[백준] 2178번: 미로탐색

문제링크 : https://www.acmicpc.net/problem/2178

 

문제풀이

bfs로 풀 수 있는 문제이다.

 

필요한 데이터

- 미로 데이터를 저장할 N x M 크기의 배열

- 칸을 방문했는지 체크하기 위한 N x M 크기의 배열

- 상하좌우 이동을 위한 방향 배열

 

1) 첫 번째 칸부터 상, 하, 좌, 우로 한 번씩 이동한다.

2) 이동한 위치가 배열의 범위 안에 들면, 이동할 수 있는 칸인지 확인한다.

   (값이 1이고, 방문하지 않은 지점이면 이동 가능)

3) 이동할 수 있는 칸이면 이동 횟수 저장 후 큐에 삽입한다.

4) 큐에 있는 요소를 제거한 후, 그 칸부터 다시 상, 하, 좌, 우로 한 번씩 이동한다.

(이하 반복)

 

따로 Point라는 클래스를 만들어 x, y, 그 칸 까지의 이동 횟수를 저장해놓았는데,

다른 블로그 글을 보니 보통 미로 배열에 횟수를 바로 저장해놓는다. 이 방법이 더 좋을 것 같다.

 

bfs로 해결되는 이유

처음에는 그 칸에 가기까지 제일 짧게 이동한 횟수를 계속해서 업데이트 해야 하지 않을까 생각했다.

하지만 그럴 필요가 없는 것이, visit 배열로 방문여부를 따로 설정하기 때문이다.

bfs는 너비 우선으로 -같은 너비 선상의 노드들 먼저- 방문하기 때문에

그 지점을 방문한 적이 있다는 것은 그 지점까지 가는 최단거리가 이미 나왔다는 뜻과 같다.

따라서 횟수를 따로 업데이트할 필요없이 구현하면 된다.

 

 

소스코드

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

public class p_2178 {
	static int N, M;
	static int[][] map;
	static boolean[][] visit;
	static int[] dx = {0, 0, -1, 1};
	static int[] dy = {1, -1, 0, 0};
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		StringTokenizer st = new StringTokenizer(str);
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		map = new int[N][M];
		visit = new boolean[N][M];
		for (int i = 0; i < N; i++) {
			str = br.readLine();
			for (int j = 0; j < M; j++) {
				map[i][j] = str.charAt(j) - '0';
			}
		}
		
		for (int i = 0; i < N; i++) {
			Arrays.fill(visit[i], false);
		}
		
		System.out.println(bfs());
	}
	
	public static int bfs() {
		int count = 0;
		Queue<Point> queue = new LinkedList<Point>();
		queue.offer(new Point(0, 0, 1));
		visit[0][0] = true;
		while (true) {
			Point p = queue.poll();
			if (p.x == N-1 && p.y == M-1) {
				count = p.dist;
				break;
			}
			
			for (int i = 0; i < 4; i++) {
				int x = p.x + dx[i];
				int y = p.y + dy[i];
				if (x >= 0 && y >= 0 && x < N && y < M) {
					if (map[x][y] == 1 && !visit[x][y]) {
						queue.offer(new Point(x, y, p.dist + 1));
						visit[x][y] = true;
					}
				}
			}
		}
		
		return count;
	}
}

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