2178번 - 미로 탐색

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

public class Main {
	
	static int[] dr = {-1, 1, 0, 0};
	static int[] dc = {0, 0, -1, 1};
	
	static class Point {
		int r;
		int c;
		
		Point(int r, int c) {
			this.r = r;
			this.c = c;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		boolean[][] map = new boolean[N][M];
		String str;
		for(int i=0;i<N;i++) {
			str = br.readLine();
			for(int j=0;j<M;j++) {
				if(str.charAt(j) == '1') {
					map[i][j] = true;
				}
			}
		}
		int cnt = 0;
		LinkedList<Point> q = new LinkedList<>();
		q.offer(new Point(0, 0));
		map[0][0] = false;
		int nr, nc, size;
		loop:
		while(!q.isEmpty()) {
			size = q.size();
			cnt++;
			for(int k=0;k<size;k++) {
				Point cur = q.poll();
				if(cur.r == N-1 && cur.c == M-1) {
					break loop;
				}
				for(int i=0;i<4;i++) {
					nr = cur.r + dr[i];
					nc = cur.c + dc[i];
					if(nr < 0 || nc < 0 || nr >= N || nc >= M) {
						continue;
					}
					if(map[nr][nc]) {
						map[nr][nc] = false;
						q.offer(new Point(nr, nc));
					}
				}
			}
		}
		System.out.println(cnt);
		br.close();
	}
}

탐색 문제에서 보통 dfs와 bfs를 떠올리게 되는데 이 경우 최소 이동 횟수를 찾아야하기 때문에 bfs를 사용해서 for문의 반복 횟수를 구하는 것이 편리합니다.

 

이 때 일반적인 bfs가 아닌 for문을 돌고 난 이후의 size만큼 for문을 돌려 각 시행단계를 분리하는 방법을 사용해야 합니다. 이렇게 하면 맨 위의 for문을 작동시킬 때마다 cnt를 올려 이동 횟수를 셀 수 있습니다.

 

또한 여기서는 visited 배열을 사용하는 대신 맵을 지날 때 0으로 표시하는 방법으로 중복 이동을 제한했습니다. 이렇게 할 경우 최단거리로 접근하는 경로만이 살아남게 되어서 더 효율적으로 탐색할 수 있습니다.