[프로그래머스] 게임 맵 최단거리 [BFS/DFS]

---

문제

 

문제 설명

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

지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다.

위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다.
아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다.

• 첫 번째 방법은 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) 위치에 있습니다.

---

입출력 예mapsanswer

[[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]]	11
[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]]	-1

입출력 예 설명

입출력 예 #1
주어진 데이터는 다음과 같습니다.

캐릭터가 적 팀의 진영까지 이동하는 가장 빠른 길은 다음 그림과 같습니다.

따라서 총 11칸을 캐릭터가 지나갔으므로 11을 return 하면 됩니다.

입출력 예 #2
문제의 예시와 같으며, 상대 팀 진영에 도달할 방법이 없습니다. 따라서 -1을 return 합니다.

 

링크 : https://school.programmers.co.kr/learn/courses/30/lessons/1844

 

---

접근 방식

처음에는 DFS로 접근하였다.

나에게는 DFS가 더 익숙하고 간단하였기 때문이다.

그리고 실제로 DFS가 개념적으로 더 이해하기 쉽다.

 

아래가 실제로 최초에 작성하였던 시간초과가 발생한 DFS 방식의 코드이다.

class Solution {
    
    int[] dx = {0,0,-1,1}; //상하좌우
    int[] dy = {-1,1,0,0}; //상하좌우
    
    int[][] path;
    int[][] maps;
    
    public int solution(int[][] maps) {
        
        this.maps = maps;
        this.path = new int[maps.length][maps[0].length];
        this.path[maps.length-1][maps[0].length-1] = -1; //도착 지점의 거쳐온 칸수를 최초에 -1로 초기화한다
        this.path[0][0] = 1; //최초 시작 지점의 거쳐온 칸수를 1로 초기화 해준다. 그리해야 최초 칸도 거쳐온 칸수에 포함된다.
        dfs(0,0);
        
        return this.path[maps.length-1][maps[0].length-1];
    }
    
    private void dfs(int x, int y)
    {
        if(x == this.maps[0].length-1 && y == this.maps.length-1) //도착 지점일 경우 더 이상 탐색하지 않도록 리턴
        {
            return;
        }
    
        for(int i = 0; i < 4; i++)
        {
            int nextX = x + dx[i];
            int nextY = y + dy[i];
            int nextPathCtn = path[y][x] + 1; //현재까지 거쳐온 칸수+1
            
            if(nextX >= 0 && nextY >= 0 && nextX < this.maps[0].length && nextY < this.maps.length)
            {            
                if(maps[nextY][nextX] == 1)
                {       
                	//현재까지 거쳐온 칸수+1이 다음에 가려는 칸에 기록된 거쳐온 칸수 보다 작거나
                    //아예 방문한적이 없는 칸이거나
                    //도착칸일 경우
                    if(nextPathCtn <= path[nextY][nextX] || path[nextY][nextX] == 0 || path[nextY][nextX] == -1) 
                    {
                        path[nextY][nextX] = nextPathCtn;
                        dfs(nextX,nextY);
                    }
                }
            }
        }
    }
}

나름 DP처럼 이차원 배열의 각 요소에 거쳐온 칸의 누적값을 저장하며(path배열),

우회하여 거쳐와서 칸 수가 더 많은 상태일 경우는 더 이상 진행하지 않도록 시간적 효율을 노렸다. 

하지만 이렇게 하여도 정확성은 통과되지만 효율성(속도)에서 시간초과로 통과하지 못했다...

물론 일반적인 DFS 방식 보다는 효율이 높지만, 통과 기준에는 만족하지 못하는것이다.

그리하여 BFS 방식으로 생각해보게 되었다.

 

BFS와 DFS의 특징은 다음과 같다.

• 단순히 모든 정점을 방문해야하는 경우는 DFS, BFS 상관없다.
• 최단거리 구하기, 미로와 같은 경우 BFS가 유리 하다.
  왜냐하면 DFS의 경우 개발자가 정의한 우선순위 방향에 따라 임의의 순서대로 깊이 탐색을 하며, 모든 경우를 다 탐색하여야지만 최단거리를 구할 수 있지만, BFS는 한 깊이마다 방문 가능한 노드(위치)를 모두 방문하여, 가장 작은 깊이에서 도착한(최단 거리) 경우의 수를 구하기 때문이다. 

그리하여 BFS로 푼 코드는 풀이에 적혀있는 대로이다.

---

풀이

 

BFS 방식의 정답 풀이

import java.util.*;

class Solution {

    public int solution(int[][] maps) {

        int[] dx = {0,0,-1,1}; //상하좌우
        int[] dy = {-1,1,0,0}; //상하좌우
        int[][] pathCtn = new int[maps.length][maps[0].length];
        pathCtn[0][0] = 1; //최초 시작 위치만 1로 초기화

        Queue<Integer[]> queue = new LinkedList<Integer[]>();
        queue.offer(new Integer[]{0,0});

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

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

            for(int i = 0; i < 4; i++)
            {
                int nx = curPst[0] + dx[i];
                int ny = curPst[1] + dy[i];
                int nPathCtn = pathCtn[curPst[1]][curPst[0]] + 1;

                if(nx >= 0 && ny >= 0 && nx <= maps[0].length-1 && ny <= maps.length-1){
                    if(maps[ny][nx] == 1 && (pathCtn[ny][nx] == 0 || nPathCtn < pathCtn[ny][nx])) // (1)  nPathCtn < pathCtn[ny][nx]) 에서 <= 로 조건을 달게 되면 특정 위치에 오기까지만 다르고 이후의 경로는 완전 똑같은 경우 경로까지 모두 재 탐색을 하게 된다.. 그러므로 꼭 =을 빼줘야한다
                    {
                        pathCtn[ny][nx] = nPathCtn;
                        queue.offer(new Integer[]{nx,ny});
                    }
                }
            }
        }

        if(pathCtn[maps.length-1][maps[0].length-1] != 0) //도착 지점이 최초값인 0이 아닌 경우, 방문한 것이기 때문에
            return pathCtn[maps.length-1][maps[0].length-1]; 
        else //방문조차 못한 경우
            return -1;
    }

}

pathCtn이란 배열에 해당 위치까지 오기까지 거쳐온 칸수를 누적한다는 점은 같다.

하지만 BFS 방식이기 때문에, 한 깊이 한 깊이를 탐색하기 때문에 가장 먼저 도착지점에 도착하게 된 경우가 바로 최단거리라는 것을 알 수 있다.

그리고 중요한 점은 

코드상에 (1)로 주석이 되어 있는 아래의 조건문이다.

 if(maps[ny][nx] == 1 && (pathCtn[ny][nx] == 0 || nPathCtn < pathCtn[ny][nx]))

만약 해당 조건문의 nPathCtn < pathCtn[ny][nx] 부분에서 부등호를 <= 로 할 경우, 같은 경로를 여러번 탐색할 경우가 발생한다.

예를 들어, 아래와 같은 맵이 있고

시작은 최상단 좌측 (0,0) 이고 도착은 최하단 우측이다 (3,3)이다.

이 경우 (1,1) 로 갈 수 있는 경로는 (0,1) 에서 가는 경우와 (1,0)에서 가는 경우가 있을 것이다.

그리고 해당 경로에서 (1,1)로 갈 경우 누적되는 칸수는 3으로 동일하다. 그리고 이후부터는 동일한 경로를 2번 탐색하게 될 것이다.

이런 경우는 탐색에서 제외시키기 위해 반드시 < 부등호로만 해주어야 한다.

 

1	1	0	0
1	1	0	0
0	1	1	1
0	0	0	1

 

 

---

참조

BFS와 DFS의 특징

https://velog.io/@lucky-korma/DFS-BFS%EC%9D%98-%EC%84%A4%EB%AA%85-%EC%B0%A8%EC%9D%B4%EC%A0%90#dfs%EC%99%80-bfs%EC%9D%98-%EC%8B%9C%EA%B0%84%EB%B3%B5%EC%9E%A1%EB%8F%84