[백준 알고리즘] Q2178 미로탐색 - BFS 너비탐색 알고리즘

1. Java 구현

           
package Q2178;

import java.io.*;
import java.util.Queue;
import java.util.concurrent.ConcurrentLinkedQueue;

public class Main {

    /*
	 	문제 : 미로탐색
	 	url : https://www.acmicpc.net/problem/2178
	 	재풀이 : O
	*/
    private static boolean isComplete = false;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 1. 입력 초기화 //
        String[] line = br.readLine().split(" ");
        int m = Integer.parseInt(line[0]);
        int n = Integer.parseInt(line[1]);
        boolean[][] maze = new boolean[m][n];
        for (int i = 0; i < maze.length; i++) {
            char[] splited = br.readLine().toCharArray();
            for (int j = 0; j < splited.length; j++) {
                maze[i][j] = splited[j] == '1' ? true : false;
            }
        }

        // 2. BFS 알고리즘 //
        boolean[][] visited = new boolean[m][n];
        int[][] result = new int[m][n];
        Queue xs = new ConcurrentLinkedQueue<>();
        Queue ys = new ConcurrentLinkedQueue<>();

        visited[0][0] = true;
        xs.add(0);
        ys.add(0);
        result[0][0] = 1;

        while(!xs.isEmpty()) {
            int x = xs.poll();
            int y = ys.poll();
            if(y > 0 && maze[y - 1][x] && visited[y - 1][x] == false) {
                plus(visited, xs, ys, result, x, y - 1, result[y][x]);
            }
            if(y < maze.length - 1 && maze[y + 1][x] && visited[y + 1][x] == false) {
                plus(visited, xs, ys, result, x, y + 1, result[y][x]);
            }
            if(x > 0 && maze[y][x - 1] && visited[y][x - 1] == false) {
                plus(visited, xs, ys, result, x - 1, y, result[y][x]);
            }
            if(x < maze[0].length - 1 && maze[y][x + 1] && visited[y][x + 1] == false) {
                plus(visited, xs, ys, result, x + 1, y, result[y][x]);
            }
        }

        bw.write(result[m - 1][n - 1] + "\n");
        bw.close();


    }

    public static void plus(boolean[][] visited, Queue xs, Queue ys, int[][] result, int x, int y, int prevNode) {
        visited[y][x] = true;
        xs.add(x);
        ys.add(y);
        result[y][x] = prevNode + 1;
    }
}

2. 코드설명

 이 문제도 바이러스 문제(Q2606) 와 동일하게 BFS 너비탐색 알고리즘을 이용해서 풀어야 한다. (Q2606 을 클릭하면 해당 문제 풀이로 이동 가능) 

 이 문제는 DFS 깊이탐색 알고리즘이 아닌, BFS 너비탐색 알고리즘을 풀어야 한다. 그 이유는, 목적지까지의 최단경로를 구해야 하기 때문에 출발지부터 

 목적지까지 너비(경로)가 몇 개인지 카운트해야 하기 때문이다. 물론 DFS로도 풀 수 는 있겠지만 BFS 로 푸는것이 효율적이라고 생각한다. 

 BFS에 대한 동작 순서는 바이러스 문제(Q2606) 에서 그림을 통해 설명했기 때문에 바이러스 문제(Q2606) 참고하면 될거 같다!

3. Pain Point

 이 문제를 푸는데 생각보다 시간이 걸렸다. 단순한 BFS 문제인데, 최단경로를 계속 고민하다 보니 엉뚱한 풀이를 작성했다. 

 이 문제를 풀면서 BFS에 대한 개념을 확고하게 잡을 수 있었다!