[백준] 2178번 : 미로 탐색

2178번: 미로 탐색

---

문제

---

예제

---

풀이

해당 문제도 DFS와 BFS를 둘 다 사용해도 되지만 DFS로 풀게 되면 시간초과가 발생한다.

그렇기에 DFS보다 비교적 계산속도가 빠른 BFS를 통해서 문제를 해결해야한다.

[백준] 1260번 : DFS와 BFS

public static void BFS(int x, int y) {
    Queue<int[]> q = new LinkedList<>();
    q.add(new int[] { x, y });

    while (!q.isEmpty()) {
        int now[] = q.poll();
        int nowX = now[0];
        int nowY = now[1];

        for (int i = 0; i < 4; i++) {
            int nextX = nowX + dx[i];
            int nextY = nowY + dy[i];

            if (nextX < 0 || nextY < 0 || nextX >= n || nextY >= m)
                continue;
            if (visit[nextX][nextY] || check[nextX][nextY] == 0)
                continue;

            q.add(new int[] {nextX, nextY});
            check[nextX][nextY] = check[nowX][nowY] + 1;
            visit[nextX][nextY] = true;
        }
    }
}

상하좌우를 가리키는 배열 dx와 dy를 통해서 네 방향을 확인한 후,

조건문을 통해서 이동할 수 있는 배열이라면 큐에 추가해 주고 visit[][]을 true로 변경해 주면 된다.

그리고 check배열의 [n-1][m-1]을 출력해 주면 해당 값이 출력된다.

---

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


public class Main {

    static int[][] check;
    static int n;
    static int m;
    static boolean[][] visit;
    static int[] dx = { -1, 1, 0, 0 }; // x방향배열 - 상하
    static int[] dy = { 0, 0, -1, 1 }; // y방향배열 - 좌우

    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());

        check = new int[n][m];

        for (int i = 0; i < n; i++) {
            String num = br.readLine();
            for (int j = 0; j < m; j++) {
                check[i][j] = num.charAt(j) - '0';
            }
        }

        visit = new boolean[n][m];
        visit[0][0] = true;
        BFS(0,0);
        System.out.println(check[n-1][m-1]);

    }

    public static void BFS(int x, int y) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] { x, y });

        while (!q.isEmpty()) {
            int now[] = q.poll();
            int nowX = now[0];
            int nowY = now[1];

            for (int i = 0; i < 4; i++) {
                int nextX = nowX + dx[i];
                int nextY = nowY + dy[i];

                if (nextX < 0 || nextY < 0 || nextX >= n || nextY >= m)
                    continue;
                if (visit[nextX][nextY] || check[nextX][nextY] == 0)
                    continue;

                q.add(new int[] {nextX, nextY});
                check[nextX][nextY] = check[nowX][nowY] + 1;
                visit[nextX][nextY] = true;
            }
        }
    }
}

---

참고

[백준 2178] 미로 탐색(Java)