[백준] 2178. 미로 탐색

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

최소 거리를 구하는 문제이기 때문에 bfs를 사용하면 된다. 관건은 이동한 칸수를 계산하는 것인데, visited 배열에 1, 2, 3, ... 과 같이 이동한 칸수를 기록해주면 된다. 즉 visited 배열의 값이 0이면 아직 방문하지 않은 위치인 것이고, 시작 위치와 같이 한 번만에 방문하면 1, 그 다음으로 방문하면 2를 기록해주면 된다. 그리고 visited 배열의 값이 0이 아닌 경우, 즉 이미 방문한 경우에는 제외하기 때문에 한 번 최단 거리로 기록된 값은 갱신되지 않는다.

import java.io.BufferedReader;
import java.io.IOException;

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

// 시간복잡도: O(V + E)
// = O(n * m + 4V)
// = 10,000 + 40,000 = 50,000
public class Main {

    static int n; // 세로
    static int m; // 가로
    static int[][] map;
    static int[][] visited;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};

    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];
        visited = new int[n][m];

        for (int i = 0; i < n; i++) {
            String[] arr = br.readLine().split("");
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(arr[j]);
            }
        }

        bfs();
        System.out.println(visited[n - 1][m - 1]);
    }

    private static void bfs() {
        Queue<Pair> que = new LinkedList<>();
        que.offer(new Pair(0, 0));
        visited[0][0] = 1; // 시작위치도 포함

        while (!que.isEmpty()) {
            Pair pair = que.poll();
            if (pair.x == m - 1 && pair.y == n - 1) {
                return;
            }

            for (int i = 0; i < 4; i++) {
                int nx = pair.x + dx[i];
                int ny = pair.y + dy[i];

                // 그래프 범위를 넘어가거나 이미 방문했으면(0이 아니면) pass
                if (nx < 0 || nx >= m || ny < 0 || ny >= n || visited[ny][nx] != 0) {
                    continue;
                }

                if (map[ny][nx] == 1) {
                    que.offer(new Pair(nx, ny));
                    visited[ny][nx] = visited[pair.y][pair.x] + 1; // 이전 위치 + 1
                }
            }
        }
    }

    static class Pair {
        int x, y;

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