[BOJ] 2178 미로탐색

 

 

[문제]

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

 

 

[소스 코드]

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

public class Main {
	static int[] dr = {-1,1,0,0};
	static int[] dc = {0,0,-1,1};
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int[][] map = new int[n][m];
		for(int i=0;i<n;i++) {
			String str = br.readLine();
			for(int j=0;j<m;j++) {
				map[i][j] = str.charAt(j) - '0';
			}
		}
		Queue<int[]> q = new LinkedList<>();
		boolean[][] visit = new boolean[n][m];
		q.offer(new int[] {0,0,1});
		visit[0][0] = true;
		while(!q.isEmpty()) {
			int[] curr = q.poll();
			if(curr[0]==n-1 && curr[1]==m-1) {
				System.out.println(curr[2]);
				return;
			}
			for(int d=0;d<4;d++) {
				int nr = curr[0] + dr[d];
				int nc = curr[1] + dc[d];
				if(nr<0 || nr>=n || nc<0 || nc>=m || visit[nr][nc]) continue;
				if(map[nr][nc]==1) {
					visit[nr][nc] = true;
					q.offer(new int[] {nr,nc,curr[2]+1});
				}
			}
		}
	}
}