[DFS/BFS] 프로그래머스 1844번 게임 맵 최단거리(Java)

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

프로그래머스

📚 문제

ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다.
지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다.

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

• 첫 번째 방법은 11개의 칸을 지나서 상대 팀 진영에 도착했습니다.

• 두 번째 방법은 15개의 칸을 지나서 상대팀 진영에 도착했습니다.

위 예시에서는 첫 번째 방법보다 더 빠르게 상대팀 진영에 도착하는 방법은 없으므로, 이 방법이 상대 팀 진영으로 가는 가장 빠른 방법입니다. 만약, 상대 팀이 자신의 팀 진영 주위에 벽을 세워두었다면 상대 팀 진영에 도착하지 못할 수도 있습니다. 예를 들어, 다음과 같은 경우에 당신의 캐릭터는 상대 팀 진영에 도착할 수 없습니다.

게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.

 

📝 문제 해결

BFS는 시작 지점에서 가까운 노드부터 차례대로 탐색하는 알고리즘으로 최단경로 문제를 풀 때 효과적이다.

1. (0, 0) 노드부터 큐에 삽입해주고

2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 벽이 아니고 아직 방문하지 않은 노드가 있다면 삽입해주고 카운트 + 1을 해주고

3. 큐에 더이상 탐색할 노드가 없을 때까지 반복해주다가 상대방 진영에 도달했을 때 카운트값을 return해준다.

 

💻 코드

import java.util.*;

class Solution {
    public static int n, m;
    public static int answer = -1;
    
    public static int dx[] = {-1, 1, 0, 0};
    public static int dy[] = {0, 0, -1, 1};
    public static boolean visited[][];
    
    public int solution(int[][] maps) {
        n = maps.length;
        m = maps[0].length;
        visited = new boolean[n][m];
    
        return bfs(0, 0, maps);
    }
    
    public int bfs(int x, int y, int[][] maps){
        Queue<int[]> que = new LinkedList<>();
    
        que.add(new int[]{x, y, 1});
        visited[0][0] = true;

        while (!que.isEmpty()) {
            int temp[] = que.poll();
            x = temp[0];
            y = temp[1];
            int count = temp[2];
            
            if (x == n-1 && y == m-1) {
                answer = count;
                break;
            }

            for (int i = 0; i<4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                if(maps[nx][ny] == 0) continue;
                if(!visited[nx][ny] && maps[nx][ny] == 1) {
                    visited[nx][ny] = true;
                    que.add(new int[]{nx, ny, count+1});
                }
            }
        }

        return answer;
    }
}

 

🔽 DFS 풀이

정확성은 통과하는데 효율성에서 탈락.. 좀 더 생각해봐야겠다..

import java.util.*;

class Solution {
    public static int n, m;
    public static int answer = Integer.MAX_VALUE;
    
    public static int dx[] = {-1, 1, 0, 0};
    public static int dy[] = {0, 0, -1, 1};
    public static boolean visited[][];
    public static int[][] count;
    
    public int solution(int[][] maps) {
        n = maps.length;
        m = maps[0].length;
        visited = new boolean[n][m];
        count = new int[n][m];
        
        visited[0][0] = true;
        count[0][0] = 1;
        
        dfs(0, 0, maps);
        
        return answer == Integer.MAX_VALUE ? -1 : answer;
    }
    
    public void dfs(int x, int y, int[][] maps){
        if(count[x][y] > answer) return;
        if(x == n-1 && y == m-1){
            answer = Math.min(answer, count[x][y]);
            return;
        }
        
        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            
            if(maps[nx][ny] == 0) continue;
            
            if(!visited[nx][ny] && maps[nx][ny] == 1){
                visited[nx][ny] = true;
                count[nx][ny] = count[x][y] + 1;
                dfs(nx, ny, maps);
                visited[nx][ny] = false;
            }
        }
    }
}