[JAVA/알고리즘] 너비 우선 탐색 BFS (백준 14940)

너비 우선 탐색 BFS란, 

시작 정점을 방문한 수 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서 너비 우선 탐색 적용.

 

Queue를 사용하여 구현

 

// 그래프 표현 (다른 자료형을 이용할 수도 있음)
private static ArrayList<ArrayList<Integer>> graph;
// 깊이 표현
private static int[] visited;

private static void BFS(int now) {
    Queue<Integer> queue = new LinkedList<>();
    visited[now] = 1;
    while (!queue.isEmpty()) {
        now = queue.poll();
        // now에 인접한 모든 노드에 대하여
        for(int next : graph.get(now)) {
            // 방문한 적이 없는 경우
            if (visited[next] == 0) {
                // 현재 깊이 + 1
                visited[next] = visited[now] + 1;
                queue.add(next);
            }
        }
    }
}

 

 

---

[백준 14940] 쉬운 차단 거리

 

 

위의 문제는 BFS를 이용하여 문제를 해결할 수 있다. 

지도를 목적지를 최상위 노드인 그래프로 생각하고 목적지를 시작점으로 BFS를 진행하면 문제를 해결할 수 있다.

 

 

public class Main {
    private static int[][] map;
    // 상하좌우 좌표 표현
    private static int[] dx = {1, 0, -1, 0};
    private static int[] dy = {0, 1, 0, -1};
    
    private static int n;
    private static int m;
    
    private static int[][] visited;
    
    private static int destX;
    private static int destY;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        map = new int[n][m];
        for(int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] == 2) {
                    destX = j;
                    destY = i;
                }
            }
        }

        visited = new int[n][m];
        BFS();

		// 목적지에 도달할 수 없는 경우 -1
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                if (map[i][j] == 1 && visited[i][j] == 0) {
                    visited[i][j] = -1;
                }
            }
        }

        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                System.out.print(visited[i][j] + " ");
            }
            System.out.println();
        }
    }


    private static void BFS() {
        Integer[] now = new Integer[] {destX, destY};
        Queue<Integer[]> queue = new LinkedList<>();
        queue.add(now);
        while (!queue.isEmpty()) {
            now = queue.poll();
            // 인접 노드 (상하좌우)
            for(int i=0; i<4; i++) {
                int x = now[0] + dx[i];
                int y = now[1] + dy[i];

                if ((0 <= x && x < m) && (0 <= y && y < n)) {
                    if (map[y][x] != 0 && visited[y][x] == 0) {
                        visited[y][x] = visited[now[1]][now[0]] + 1;
                        queue.add(new Integer[] {x, y});
                    }
                }
            }
        }
        visited[destY][destX] = 0;
    }
}

 

한 노드에 대하여 인접한 노드는 그 노드의 상하좌우에 있는 노드들이기 때문에 상하좌우의 노드들을 탐색한다. 

 

주의 할 점은 BFS()를 빠져나온 이 후, map[][]의 값은 1이지만 visited[][]값이 0인 값들 (원래 갈 수 있는 땅이나 목적지에 도달할 수 없는 땅)을 -1로 값을 지정해줘야 한다. 

 

 

 

<참고자료>

https://www.youtube.com/watch?v=-zGFtwIiJ4s&list=PLiZcqApxCH41OvXa9Hl-SRaHM2HEohRSQ