[백준] 2178번 - 미로 탐색

 

최소 탐색을 해야 하는 문제이므로 BFS로 문제를 풀이하였다. 기본적으로 지나갈 수 있는 값이 1이므로, 이 값에서 1씩 증가시키는 식으로 배열을 수정하여서 마지막 노드의 값을 출력하도록 하였다.

 

종종 최소탐색 문제를 DFS로 풀어서 시간초과가 나곤 하는데 이런 경우 모든 경로를 탐색하기 때문에 BFS를 사용하여 풀이하는 것이 적절하다.

 

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

class Dot {
	int x;
	int y;

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

public class p2178 {
	public static int row;
	public static int col;

	public static int[][] ary;
	public static boolean[][] visited;

	public static int[] nx = { -1, 0, 0, 1 };
	public static int[] ny = { 0, 1, -1, 0 };

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		row = Integer.parseInt(st.nextToken());
		col = Integer.parseInt(st.nextToken());

		ary = new int[row][col];

		visited = new boolean[row][col];

		for (int i = 0; i < row; i++) {
			String[] s = br.readLine().split("");
			for (int j = 0; j < col; j++) {
				ary[i][j] = Integer.parseInt(s[j]);
			}
		}
		bfs(0, 0);

		System.out.println(ary[row - 1][col - 1]);

	}

	public static void bfs(int x, int y) {
		Queue<Dot> q = new LinkedList<>();
		q.add(new Dot(x, y));

		while (!q.isEmpty()) {
			Dot n = q.poll();
			for (int i = 0; i < 4; i++) {
				int x_ = n.x + nx[i];
				int y_ = n.y + ny[i];
				if (x_ >= 0 && x_ < row && y_ >= 0 && y_ < col) {
					if (visited[x_][y_] == false && ary[x_][y_] == 1) {
						ary[x_][y_] = ary[n.x][n.y] + 1;
						q.add(new Dot(x_, y_));
					}
					visited[x_][y_] = true;
				}
			}
		}
	}
}