돌고 돌아 기본

프로그래머스 1844번 - 게임 맵 최단거리 요구사항 1. 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 반환하라. 2. 검은색 부분은 벽이며, 벽으로 막힌 칸은 지나갈 수 없습니다. 3. 게임 맵을 벗어난 칸은 갈 수 없습니다. 4. 캐릭터는 (1, 1) 위치에 있으며, 상대 팀 진영은 (n, m) 위치에 있습니다. 요구사항 분석 및 풀이과정 1. 이 문제와 같은 방법으로 풀면 됩니다. 2. 다른 점은 그래프(또는 트리)로 구성된 것이 아니라 배열로 구성되어있다는 점입니다. 3. 게임 맵을 벗어나지 않고, 벽으로 막힌 칸은 지나갈 수 없는 점을 고려하여 4방향으로 BFS 탐색을 진행하면 됩니다. 4-1. 각 칸에 처음 도착했을 시점에 지나온 칸의 개수가 캐릭터의 시작 점에..

프로그래머스 43105번 - 정수 삼각형 요구사항 1. 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 최댓값을 반환하라. 2. 단, 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 요구사항 분석 및 풀이과정 1. 주어진 삼각형은 시각적인 표현이고, 삼각형을 배열로 보면 다음과 같습니다. 2. 시각적으로 표현된 삼각형 기준으로 아래 칸으로 이동할 때 대각선 방향으로 한 칸 오른쪽 또는 왼쪽이기 때문에, 위 모양을 기준으로는 아래 방향 또는 우측 하단 대각선 방향으로만 이동이 가능합니다. 3. 2번을 경유해오는 칸을 도착하는 칸을 시점으로 보면 왼쪽 상단 대각선 방향 또는 위쪽 방향에서 올 수 있습니다. 그림으로 표현해보면 다음과 같습니다. 4. 3번..

프로그래머스 42898번 - 등굣길 요구사항 1. 물에 잠기지 않은 지역을 통해 학교로 가려고 합니다. 단, 오른쪽과 아래쪽으로만 움직일 수 있습니다. 2. 집에서 학교까지 갈 수 있는 최단경로의 개수를 1, 000, 000, 007로 나눈 나머지를 반환하라. 요구사항 분석 및 풀이과정 1. 오른쪽과 아래쪽으로만 움직일 수 있다는 뜻은 특정 지역을 기준으로 해당 지역으로 들어오는 방향이 왼쪽과 위쪽밖에 없다는 것을 의미합니다. 2. 따라서 집에서 각 지역까지 갈 수 있는 최단경로의 개수를 dp[지역]이라고 하면 다음과 같습니다. dp[지역] = dp[왼쪽 지역] + dp[위쪽 지역] 3. dp[지역]을 코드로 옮기기 위하여 지역을 좌표 정보로 표현하여 점화식을 정리하면 다음과 같습니다. 단, 집의 위치는..

프로그래머스 42861번 - 섬 연결하기 요구사항 1. 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 반환하라. 2. A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다. 요구사항 분석 및 풀이과정 1. 이 문제는 전형적인 최소 스패닝 트리 문제입니다. 최소 스패닝 트리 문제는 크루스칼 알고리즘 또는 프림 알고리즘으로 해결 가능합니다. 2. 저는 서로소 집합(Union-Find)을 이용한 크루스칼 알고리즘을 사용할 할 것입니다. 크루스칼 알고리즘에 대해서는 따로 설명하지 않겠습니다. 3. 섬 사이에 다리를 건설하는 비용을 기준으로 내림차순 정렬하여, 비용이 적은 다리부터 사이클이 형성되지 않도록 N - 1 개의 ..

프로그래머스 42577번 - 전화번호 목록 요구사항 1. 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있으면 false, 그렇지 않으면 true를 반환하라. 요구사항 분석 및 풀이과정 1. 보는 관점을 바꾸면 풀이가 쉬워진다. 한 번호가 다른 번호의 접두어인 경우가 있는가 한 번호의 접두어가 될 수 있는 문자열 중 전화번호부에 있는 번호가 있는가 2. 전화번호부에 특정 번호가 있는지 빠르게 확인하기 위하여 전화번호부를 Set(HashSet)을 이용하여 만들어줍니다. 3. 전화번호부에 등록된 번호를 순회하면서 해당 번호의 모든 접두어에 대하여 전화번호부에 있는 번호인지를 검사합니다. 그림으로 살펴보면 다음과 같습니다. 전화번호부는 ["12", "123", "1235"]라고 해보겠..