[백준 2178] 미로탐색

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

대표적인 BFS 문제입니다.

좌표 저장용 노드 클래스,

미로를 저장할 배열,

방문했는지 여부용 배열을 사용하고

반복문으로 상하좌우 탐색용 배열2개를 사용합니다.

1. 입력받은 미로로 부터 1, 1을 방문체크 하고 큐에 넣어 시작

2. 큐에 원소가 있을동안 큐에서 하나 빼고 

   poll한 노드의 상하좌우 좌표를 체크하고 이것이 

   2-1. 미로의 크기를 벗어나지 않음

   2-2. 미로의 길임

   2-3. 길이 아직 방문이 안되있음

3. 이 세가지 조건을 만족할 경우 다음 좌표를 방문체크 후, 미로의 값을 1 늘려주고

   해당 좌표를 가진 노드를 생성해 큐에 넣어줍니다. 

2~3을 반복.

 

public class Q2178 {
	public static int[] nX = {-1, 0, 1, 0};
	public static int[] nY = {0, -1, 0, 1};
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());
		
		int[][] arr = new int[a][b];
		int[][] visited = new int[a][b];
		
		String str;
		for(int i=0; i<arr.length; i++) {
			str = br.readLine();
			char[] temp = str.toCharArray();
			for(int j=0; j<arr[0].length; j++) {
				arr[i][j] = temp[j]-48;
			}
		}
		
		Queue<Node> q = new LinkedList<Node>();
		q.add(new Node(0, 0));
		visited[0][0] = 1;
		int nextX = 0;
		int nextY = 0;
		while(!q.isEmpty()) {
			Node current = q.poll();
			for(int i=0; i<4; i++) {
				nextX = current.x + nX[i];
				nextY = current.y + nY[i];
				if(nextX<0 || nextY<0 || nextX>=a || nextY>=b) {
					continue;
				}
				if(arr[nextX][nextY]==0) {
					continue;
				}
				if(visited[nextX][nextY]==1) {
					continue;
				}else {
					visited[nextX][nextY]=1;
					arr[nextX][nextY] = arr[current.x][current.y]+1;
					q.add(new Node(nextX, nextY));
				}
			}
		}
		
		System.out.print(arr[a-1][b-1]);
	}
}
class Node{
	int x;
	int y;
	public Node(int x, int y) {
		this.x = x;
		this.y = y;
	}
}