[Algorithm] 백준 알고리즘 2178 (미로찾기)

 

java코드

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

public class FindMaze{
	
	static int N, M;
	static int maze[][];
	static boolean visited[][];
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		maze = new int[N][M];
		visited = new boolean[N][M];
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			String line = st.nextToken();
			for(int j=0; j<M; j++) {
				maze[i][j] = line.charAt(j)-'0';
			}
		}
		
		solve();
		System.out.println(maze[N-1][M-1]);
	}
	static void solve() {
		
		int dx[] = {-1, 1, 0, 0};
		int dy[] = {0, 0, 1, -1};
		
		Queue<int[]> q = new LinkedList<>();
		q.add(new int[] {0,0});
		visited[0][0] = true;
        
		while(!q.isEmpty()) {
			int location[] = q.poll();
			int x = location[0];
			int y = location[1];
			
			for(int i=0; i<4; i++) {
				int xx = x+dx[i];
				int yy = y+dy[i];
				if(xx>=0&&xx<N&&yy>=0&&yy<M) {
					if(maze[xx][yy]!=0&&!visited[xx][yy]) {
						q.add(new int[] {xx,yy});
                        visited[xx][yy]=true;
						maze[xx][yy] = maze[x][y]+1;
					}
				}
			}
		}
		
	}
}