BFS 백준 알고리즘 자바 2178 ‘미로탐색’ 문제풀이

Problem

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

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

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

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

Solution

이전에 풀었던 BFS와 푸는 방식이 동일하다. 다만 그동안 구한 값 중 최소 값을 구해야 한다는 점과, 입력 형식이 띄어쓰기가 없어서 nextInt()가 안 된다는 점이 다르다. (그래서 trim과 문자 변형 단계를 거쳤다.)

Code

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt(), m = scan.nextInt(); scan.nextLine();
		int min = Integer.MAX_VALUE;
		
		boolean[][] v = new boolean[n][m];
		int[][] maze = new int[n][m];
		for(int i = 0; i < n; i++) {
			char[] tmp = scan.nextLine().trim().toCharArray();
			for(int j = 0; j < m; j++)
				maze[i][j] = Character.getNumericValue(tmp[j]);
		}
		
		Queue qx = new LinkedList<>();
		Queue qy = new LinkedList<>();
		qx.add(0); qy.add(0);
		
		int[] dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};
		int x, y, _x, _y;
		while(!qx.isEmpty()) {
			x = qx.poll(); y = qy.poll();
			v[y][x] = true;
			
			for(int i = 0; i < 4; i++) {
				_x = x + dx[i]; _y = y + dy[i];
				
				if(_x < 0 || _y < 0 || _x >= m || _y >= n)
					continue;
				if(maze[_y][_x] == 1 && !v[_y][_x]) {
					qx.add(_x); qy.add(_y);
					v[_y][_x] = true;
					maze[_y][_x] += maze[y][x];
					
					if(_x == m-1 && _y == n-1)
						min = Math.min(min, maze[_y][_x]);
				}
			}
		}
		System.out.println(min);
	}
}