[Java/백준/BFS] 2178번: 미로 탐색

문제

www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

코드

최단거리는 BFS로 푸는 것이 좋다. 한 노드에서 연결된 각 노드들을 동시에 검사하기 때문이다.

이 문제에서의 visited는 boolean[][]이 아닌 int[][]이다. (지나갔는지 체크하는 용도가 아니라 몇칸 옮겼는지 기록하는 역할)

(0,0)에서 시작해 (n-1,m-1)까지 BFS로 검사하다 제일 먼저 (n-1,m-1)에 도착하는 경로가 있으면 visited[n-1][m-1]에 입력된다.

다른 경로로 visited[n-1][m-1]에 도달한다 해도 그 값이 0이 아니니 쓰여지지 않는다.

 

cnt 는 1부터 시작한다. 시작점과 도착점도 카운팅에 포함한다고 했기 때문이다.

 

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

class Node{
	int x;
	int y;
	Node(int x, int y){
		this.x = x;
		this.y = y;
	}
}
public class Main {
	static int n;
	static int m;
	static int[][] visited;
	static int[][] maze;
	static int cnt;
	static int[] dx = {0,0,-1,1};
	static int[] dy = {-1,1,0,0};
	
	public static void bfs() {
		Queue<Node> queue = new LinkedList<>();
		cnt=1;
		visited[0][0] = cnt;
		
		queue.offer(new Node(0,0));
		while(!queue.isEmpty()) {
			Node r = queue.poll();
			int x = r.x;
			int y = r.y;
			for(int i=0; i<4; i++) {
				if(x+dx[i]<0 || x+dx[i]>=n || y+dy[i]<0 ||y+dy[i]>=m)
					continue;
				else if(maze[x+dx[i]][y+dy[i]]==1 && visited[x+dx[i]][y+dy[i]]==0) {
					visited[x+dx[i]][y+dy[i]]=visited[x][y]+1;
					queue.offer(new Node(x+dx[i],y+dy[i]));
				}
			}
		}
	}
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		String cond = br.readLine();
		n = Integer.parseInt(cond.split("\\s")[0]);
		m = Integer.parseInt(cond.split("\\s")[1]);
		maze = new int[n][m];
		visited = new int[n][m];
		for(int i=0; i<n; i++) {
			String str = br.readLine();
			for(int j=0; j<m; j++) {
				maze[i][j] = Integer.parseInt(str.substring(j,j+1));
			}
		}
		
		bfs();
		
		bw.write(Integer.toString(visited[n-1][m-1])+"\n");
		bw.flush();
		
	}
}