[백준저지] 2178번 : 미로 탐색

www.acmicpc.net/problem/2178

1. 문제

N×M크기의 배열로 표현되는 미로가 있다.

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입)

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출)

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

2. 풀이

import java.util.*;

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

public class Main {
	// 사방을 체크해야하므로
    public static final int[] dx = {0, 0, 1, -1};
    public static final int[] dy = {1, -1, 0, 0};
    public static void bfs(int[][] A, boolean[][] C, int[][] D, int x, int y, int N, int M) {
        Queue<Pair> q = new LinkedList<Pair>();
        // 일단 먼저 시작하는 정점 넣고
        q.add(new Pair(x, y));
		// 방문했다고 처리
        C[x][y] = true;
        // 시작값은 1부터 시작
        D[0][0] = 1;
        while (!q.isEmpty()) {
            // 큐에서 빼서
            Pair p = q.remove();
            x = p.x;
            y = p.y;
            // 매 노드마다 사방을 체크
            for (int k = 0; k < 4; k++) {
                int nx = x+dx[k];
                int ny = y+dy[k];
                // 기준값을 넘어가는지 체크
                if (0 <= nx && nx < N && 0 <= ny && ny < M) {
                    // 값이 1인데 방문 안한 경우
                    if (A[nx][ny] == 1 && C[nx][ny] == false) {
                        // 큐에 넣고
                        q.add(new Pair(nx, ny));
                        // 방문 처리
                        C[nx][ny] = true;
                        // 다음 스탭이므로 + 1
                        D[nx][ny] = D[x][y] + 1;
                    }
                }
            }
        }
    }
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        // 지도 값 저장
        int[][] A = new int[N][M];
        // 방문여부 값 저장
        boolean[][] C = new boolean[N][M];
        // 매 스탭마다 + 1 해주는 값.
        int[][] D = new int[N][M];
        for (int i = 0; i < N; i++) {
        	// 붙어서 입력받으므로,,
            String str = sc.next();
            // charArray로 변환 후 int값으로 변환
            char[] charArr = str.toCharArray();
            for (int j = 0; j < M; j++) {
                A[i][j] = charArr[j] - '0';
            }
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
            	// 값이 1이면서 방문 안한 노드부터 BFS
                if (A[i][j] == 1 && D[i][j] == 0) {
                    bfs(A, C, D, i, j, N, M);
                }
            }
        }
        System.out.println(D[N-1][M-1]);
    }
}

BFS를 이용해서 처리