[BOJ] 2178 미로 (Java)

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

알고리즘

BFS & DFS

풀이

1. 미로의 시작 인덱스를 큐에 넣는다.
2. 큐에서 현재 위치 좌표를 빼고, 방문 처리를 한다.
3. 현재 위치에서 갈 수 있는 다음 위치의 좌표를 큐에 넣고, 다음 위치를 방문처리한다.
4. 다음 위치의 값을 현재 위치 값+1로 초기화한다.
5. 큐가 빌 때까지 진행한다.(문제에서 무조건 미로의 길은 있다고 했으므로)

코드

import java.util.*;
import java.io.*;

public class Main_2178_미로 {

	static int N, M, map[][];
	static int dy[] = {0, 1, 0, -1}; 
	static int dx[] = {1, 0, -1, 0}; 
	static boolean v[][];
	static Queue<int[]> q;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new int[N][M];
		v = new boolean[N][M];
		
		for(int i=0; i<N; i++) {
			String line = br.readLine();
			for(int j=0; j<M; j++) {
				map[i][j] = line.charAt(j)-'0';
			}
		}
		
		q = new LinkedList<>();
		q.offer(new int [] {0, 0});
		while(!q.isEmpty()) {
			int[] cur = q.poll();
			int cy = cur[0];
			int cx = cur[1];
			v[cy][cx] = true;
	
			for(int d=0; d<4; d++) {
				int ny = cy+dy[d];
				int nx = cx+dx[d];
				
				if(ny>=0&&ny<N && nx>=0&&nx<M && map[ny][nx]!=0 && !v[ny][nx]) {
					map[ny][nx] = map[cy][cx]+1;
					q.offer(new int[] {ny, nx});
					v[ny][nx] = true;
				}
			}
		}
		System.out.println(map[N-1][M-1]);
		br.close();
	}
}