[백준] 2178번 미로 탐색 자바

문제

 

2178번: 미로 탐색

 

 

문제 풀이

 

이 문제는 진짜 BFS의 정석 같다. 

처음에 오른쪽 왼쪽으로 이동하는 것만 담았다가 벽에 막혀서 위나 왼쪽으로도 다시 올라갈 수 있다는 점을 깨닫고 다시 상하좌우로 dr, dc배열을 바꾼거랑 visited배열을 int가 아니라 boolean으로 처음 쓰고 바꾼 거 말고는 나름 빨리 푼 것 같다.

 

 

소스 코드

 

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 Main {

	static int N, M;
	static int[][] maze;
	static int[][] visited;
	static int[] dr = {-1, 1, 0, 0}; //상하좌우
	static int[] dc = {0, 0, -1, 1};
	
	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+1][M+1];
		visited = new int[N+1][M+1];
		
		for(int i = 1; i <= N; i++) {
			String[] s= br.readLine().split("");
			for(int j = 1; j <= M; j++) {
				maze[i][j] = Integer.parseInt(s[j-1]);
			}
		}
		
		bfs();
		System.out.println(visited[N][M]);
	}
	
	public static void bfs() {
		Queue<pos> q = new LinkedList<>();
		q.add(new pos(1, 1));
		visited[1][1] = 1;
		
		while(!q.isEmpty()) {
			pos p = q.poll();
			int r = p.r;
			int c = p.c;
			
			if(r == N && c == M)
				return;
			
			for(int i = 0; i < 4; i++) {
				int nextR = r + dr[i];
				int nextC = c + dc[i];
				if(nextR > 0 && nextR <= N && nextC > 0 && nextC <= M) {
					if(visited[nextR][nextC] == 0 && maze[nextR][nextC] == 1) {
						q.add(new pos(nextR, nextC));
						visited[nextR][nextC] = visited[r][c] + 1;
					}
				}
			}	
		}
		
	}

}

class pos{
	int r, c;
	public pos(int r, int c) {
		this.r = r;
		this.c = c;
	}
}