[BFS] 백준 - 2178번: 미로 탐색 Java 풀이

[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!]

 

2178번: 미로 탐색

 

 

문제는 1, 1부터 시작하여 n, m까지의 최단 거리를 BFS로 구하는 것이다.

 

BFS를 공부한 지 얼마 안 돼 디버깅하면서 풀어보니 Queue에 지점을 추가할 때 x좌표, y좌표, 카운트를 넣어줘야 하기 때문에 클래스 하나를 만들어 큐에 넣어줬다.

 

그리고 여기서 내가 고민했던 것은 만약 막힌 길로 가면 어떻게 해야 하지였는데 생각보다 간단했다.

큐의 구조를 사용하니 큐에서 빼낸 좌표가 막힌 길로 가면 그냥 그거는 없어지면 된다. 그리고 제대로 된 경로로 가는 녀석만 계속 살아남아 결국 (n, m) 좌표에 도달할 것이다!

 

위의 사진이 현재 (2, 5)와 (1, 6)이 큐에 담긴 모습이다.

(1, 6)의 경우 더 이상 갈 곳이 없다. 그래서 그냥 저거는 버려지면 되는 것이고 (1, 4)만 살려 계속 내려가면 된다.

 

코드

import java.util.*;

public class Main {
    static boolean[][] map;
    static boolean[][] visit;
    static int n;
    static int m;
    static int dx[] = {-1, 1, 0, 0};
    static int dy[] = {0, 0, -1, 1};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();
        sc.nextLine();

        map = new boolean[n][m];
        visit = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            String str = sc.nextLine();
            for (int j = 0; j < str.length(); j++) {
                if (str.charAt(j) == '1') {
                    map[i][j] = true;
                }
            }
        }

        System.out.println(bfs(0, 0));
    }

    private static int bfs(int x, int y) {
        visit[x][y] = true;
        Queue<Coordinate> q = new LinkedList<>();
        q.add(new Coordinate(x, y, 1));

        while (!q.isEmpty()) {
            Coordinate c = q.remove();

            if (c.x == n - 1 && c.y == m - 1)
                return c.c;

            for (int i = 0; i < 4; i++) {
                int nowX = c.x + dx[i];
                int nowY = c.y + dy[i];

                if (nowX >= 0 && nowY >= 0 && nowX < n && nowY < m) {
                    if (!visit[nowX][nowY] && map[nowX][nowY]) {
                        visit[nowX][nowY] = true;
                        q.add(new Coordinate(nowX, nowY, c.c + 1));
                    }
                }
            }
        }
        return 0;
    }

    static class Coordinate {
        int x;
        int y;
        int c;

        public Coordinate(int x, int y, int c) {
            this.x = x;
            this.y = y;
            this.c = c;
        }
    }
}

 

DFS만 풀다가 BFS를 공부하려니 조금 헷갈리는 부분이 있었지만 큐를 잘 사용하면 될 것 같다..!