[백준 2178] 미로 탐색 Java 풀이

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

 

접근

(1, 1)에서 출발하여 (n, m) 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하기 위해서는 BFS를 이용하여 문제를 해결할 수 있습니다.

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

class Position {
	int r, c;

	Position(int r, int c) {
		this.r = r;
		this.c = c;
	}
}

public class Main {
	static int n, m;
	static int[][] maze;

	// 상, 하, 좌, 우
	static int[] dr = { -1, 1, 0, 0 };
	static int[] dc = { 0, 0, -1, 1 };

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		// 입력 처리
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		maze = new int[n + 1][m + 1];

		for (int i = 1; i <= n; i++) {
			char[] input = br.readLine().toCharArray();
			for (int j = 1; j <= m; j++) {
				maze[i][j] = input[j - 1] - '0';
			}
		}

		// 최소의 칸 수를 구하기 위해서 bfs 수행
		bfs();

		// 결과 출력
		System.out.println(maze[n][m]);
	}

	static void bfs() {
		Queue<Position> bfsQ = new ArrayDeque<>();
		bfsQ.offer(new Position(1, 1));

		while (!bfsQ.isEmpty()) {
			Position curr = bfsQ.poll();
			for (int dir = 0; dir < 4; dir++) {
				int nr = curr.r + dr[dir];
				int nc = curr.c + dc[dir];
				if (inRange(nr, nc) && maze[nr][nc] == 1) {
					bfsQ.offer(new Position(nr, nc));
					maze[nr][nc] = maze[curr.r][curr.c] + 1;
				}
			}
		}
	}

	static boolean inRange(int r, int c) {
		return 1 <= r && r <= n && 1 <= c && c <= m;
	}
}