프로그래머스 - 게임 맵 최단거리

박상원·2023년 12월 5일

Coding Test

목록 보기

10/18

오늘 풀어본 문제는 프로그래머스의 게임 맵 최단거리라는 문제이다.
문제 설명은 다음과 같다.

문제 설명
ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다.

지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다.
[[1,0,1,1,1],
[1,0,1,0,1],
[1,0,1,1,1],
[1,1,1,0,1],
[0,0,0,0,1]]
위 배열에서 0인 부분은 벽으로 막혀있어 갈 수 없는 길이며, 1인 부분은 갈 수 있는 부분입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다.
아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다.

첫 번째 방법은 11개의 칸을 지나서 상대 팀 진영에 도착했습니다.
두 번째 방법은 15개의 칸을 지나서 상대팀 진영에 도착했습니다.
위 예시에서는 첫 번째 방법보다 더 빠르게 상대팀 진영에 도착하는 방법은 없으므로, 이 방법이 상대 팀 진영으로 가는 가장 빠른 방법입니다.
게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.

제한사항

maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.
- n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.
maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.
처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.

위 문제를 보고 풀이 방법을 생각해보니 BFS/DFS를 사용하여 풀 수 있을 것 같았다. 나는 이 두개의 풀이 방법 중 BFS를 선택하여 풀었다.

BFS를 사용하여 위치와 현재 길이를 가지고 있는 배열을 큐에 넣고 하나씩 꺼내서 주변에 있는 경로를 저장하는 방법으로 푸니 정답을 받을 수 있었다.

풀이 코드는 다음과 같다.

import java.util.*;

class Solution {
    public int solution(int[][] maps) {
        int answer = -1;
        boolean[][] visitMap = new boolean[maps.length][maps[0].length];
        Queue<Integer[]> queue = new LinkedList<>();
        queue.add(new Integer[] { 0, 0, 1 });
        visitMap[0][0] = true;

        while (!queue.isEmpty()) {
            Integer[] intArray = queue.poll();

            if (intArray[0] == maps.length - 1 && intArray[1] == maps[0].length - 1) {
                answer = intArray[2];
                break;
            }

            if (intArray[0] + 1 < maps.length && !visitMap[intArray[0] + 1][intArray[1]]
                    && maps[intArray[0] + 1][intArray[1]] == 1) {
                queue.add(new Integer[] { intArray[0] + 1, intArray[1], intArray[2] + 1 });
                visitMap[intArray[0] + 1][intArray[1]] = true;

            }

            if (intArray[1] + 1 < maps[0].length && !visitMap[intArray[0]][intArray[1] + 1]
                    && maps[intArray[0]][intArray[1] + 1] == 1) {
                queue.add(new Integer[] { intArray[0], intArray[1] + 1, intArray[2] + 1 });
                visitMap[intArray[0]][intArray[1] + 1] = true;
            }

            if (intArray[0] - 1 >= 0 && !visitMap[intArray[0] - 1][intArray[1]]
                    && maps[intArray[0] - 1][intArray[1]] == 1) {
                queue.add(new Integer[] { intArray[0] - 1, intArray[1], intArray[2] + 1 });
                visitMap[intArray[0] - 1][intArray[1]] = true;
            }

            if (intArray[1] - 1 >= 0 && !visitMap[intArray[0]][intArray[1] - 1]
                    && maps[intArray[0]][intArray[1] - 1] == 1) {
                queue.add(new Integer[] { intArray[0], intArray[1] - 1, intArray[2] + 1 });
                visitMap[intArray[0]][intArray[1] - 1] = true;
            }
        }
        return answer;
    }
}

우선 처음에 방문 처리를 위한 visitMap을 maps의 크기랑 같게 만들어 주고, 정수 배열을 받는 큐를 생성해준다.
큐는 주변에 있는 경로를 다 탐색하기 전까지는 다음 경로를 갈 수 없게 하기 위해 사용하는 것이다.

그리고 처음 위치와 현재 길이 1을 저장하는 정수 배열을 큐에 삽입해주고 첫 위치를 방문처리 해준다.

다음으로 나머지 위치들은 반복문을 통해 큐가 비어있을 때까지 반복을 하게 된다.

반복문 내부의 로직은 다음과 같다.
우선 큐의 맨 앞에 있는 값을 가져와서 그 위치가 목적지인지 확인하고 목적지가 맞으면 answer에 정수 배열 마지막에 존재하는 현재 길이의 값을 넣고 반복문을 종료한다.

위와 같이 목적지 도착 시 반복을 종료하는 이유는 현재 길이가 같은 값을 계속해서 탐색할 것이고 처음 목적지에 달성한 길이는 최솟값이 되기 때문이다.

다음으로 위치가 목적지의 위치가 아니라면 그 주변에 있는 경로가 maps내부에 존재하고 방문이 안되어있고 벽이 아니라면 방문처리 후 queue에 삽입해준다.

위 반복문이 끝나게 되면 목적지로 가는 최소 길이가 answer에 저장되거나 목적지로 갈 수 없으면 -1이 그대로 있게 된다.

그리고 이 값을 반환하게 되면 정답을 받을 수 있다.

깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)

그래프를 탐색하는 방법에는 크게 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있다.

여기서 그래프란, 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종을 말하며, 그래프를 탐색한다는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것이다.

깊이 우선 탐색(DFS, Depth-First Search)

최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동

깊이 우선 탐색의 개념
루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말한다.

예를 들어, 미로찾기를 할 때 최대한 한 방향으로 갈 수 있을 때까지 쭉 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 그 갈림길로부터 다시 다른 방향으로 탐색을 진행하는 것이 깊이 우선 탐색 방식이라고 할 수 있다.

모든 노드를 방문하고자 하는 경우에 이 방법을 선택함

깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단함

검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느림

너비 우선 탐색(BFS, Breadth-First Search)

최대한 넓게 이동한, 다음 더 이상 갈 수 없을 때 아래로 이동

너비 우선 탐색의 개념
루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법으로, 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.

주로 두 노드 사이의 최단경로를 찾고싶을 때 이 방법을 선택한다.
ex) 지구 상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Sam과 Eddie 사이에 존재하는 경로를 찾는 경우

깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모름

너비 우선 탐색의 경우 - Sam과 가까운 관계부터 탐색

깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 비교

DFS

현재 정점에서 갈 수 있는 점들 가지 들어가면서 탐색
스택 또는 재귀함수로 구현

BFS

현재 정점에서 연결된 가까운 점들부터 탐색
큐를 이용해서 구현

DFS와 BFS의 시간복잡도
두 방식 모두 조건 내의 모든 노드를 검색한다는 점에서 시간복잡도는 동일하다.
DFS와 BFS 둘 다 다음 노드가 방문하였는지를 확인하는 시간과 각 노드를 방문하는 시간을 합하면 된다.

N은 노드, E는 간선일 때

인접 리스트: O(N + E)

인접 행렬: O(N N)
일반적으로 E(간선)의 크기가 N N에 비해 상대적으로 적기 때문에 인접 리스트 방식이 효율적이다.

깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)를 활용한 문제 유형/응용

DFS, BFS는 특징에 따라 사용에 더 적합한 문제 유형들이 있다.

그래프의 모든 정점을 방문하는 것이 주요한 문제
단순히 모든 정점을 방문하는 것이 중요한 문제의 경우 DFS, BFS 두 가지 방법 중 어느 것을 사용해도 상관없다.
경로의 특징을 저장해둬야 하는 문제
예를 들면 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용한다.
최단거리를 구해야 하는 문제
미로 찾기 등 최단거리를 구해야 할 경우, BFS가 유리하다.
왜냐하면 깊이 우선 탐색으로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만, 너비 우선 탐색은 현재 노드에서 가까운 곳부터 찾기 때문에 경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리이기 때문이다.

이 외에도