프로그래머스_고득점kit_우선탐색_게임 맵 최단거리

풀이

import java.util.*;

class Solution {
    static class Node {
        int x, y, dist;
        
        Node(int x, int y, int dist) {
            this.x = x;
            this.y = y;
            this.dist = dist;
        }
    }

    public int solution(int[][] maps) {
        int n = maps.length;
        int m = maps[0].length;
        
        int[][] directions = {{1,0}, {-1,0}, {0,1}, {0,-1}}; // 상, 하, 우, 좌
        boolean[][] visited = new boolean[n][m]; // 방문 여부
        
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(0, 0, 1));
        visited[0][0] = true;
        
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            int x = node.x, y = node.y, dist = node.dist;
            
            if (x == n - 1 && y == m - 1) return dist; // 도착하면 거리 반환
            
            for (int[] dir : directions) {
                int nx = x + dir[0];
                int ny = y + dir[1];
                
                if (nx >= 0 && ny >= 0 && nx < n && ny < m) { // 범위 체크
                    if (!visited[nx][ny] && maps[nx][ny] == 1) { // 방문 안 했고 길이면
                        queue.offer(new Node(nx, ny, dist + 1));
                        visited[nx][ny] = true;
                    }
                }
            }
        }
        
        return -1; // 도착점에 도달할 수 없는 경우
    }
}

---

개념정리

❓ 너비우선탐색(BFS)

✔️ 시작으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 곳을 나중에 방문하는 순회 방법이다

✔️ 최단 거리를 찾을 때 DFS 보다 유리

✔️ Queue 를 사용하여 한 번 방문한 곳은 다시 방문하지 않도록 한다.

 

❓ BFS 에서 Queue 를 사용하는 이유

✔️ Queue 는 선입선출 방식으로 동작하기 때문에, 현재와 가장 가까운 위치부터 탐색한다.

✔️ 탐색 순서가 정해져 있기 때문에, 먼저 도착한 노드가 최단 경로로 온 노드임을 보장한다.

 

 

갈림길에서 큐가 두개 쌓이고, 그 큐를 순서대로 처리한다. 노드가 하나의 길을 끝까지 파고 돌아오는 DFS 와 달리, BFS 에서는 가까운 지점부터 우선탐색한다.

 

 

와... 이건 진짜 어려웠다ㅠㅠ