[Java][2178] 미로 탐색

문제:

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

2178번: 미로 탐색

코드:

import java.util.*;

public class Main {
	public static boolean [][] vis = new boolean[502][502];
	public static int [][] board = new int[502][502];
	public static int [][] dist = new int[502][502];
	public static int n,m; // n > 행 m > 열
	public static int [] dx = {1,0,-1,0};
	public static int [] dy = {0,1,0,-1};
    public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
    	n = sc.nextInt();
    	m = sc.nextInt();
    	
    	for(int i=0;i<n;i++) {
    		String s = sc.next();
    		for(int j=0;j<s.length();j++) {
    			board[i][j] = s.charAt(j)-'0';
                // 수들이 붙어서 입력되기에 charAt 사용
    		}
    	}
    	
    	Queue<Pos> q = new LinkedList<>();
    	
    	vis[0][0] = true; // 방문 확인
    	q.add(new Pos(0,0));
    	dist[0][0] = 1; // 거리확인
    		    	
    	while(!q.isEmpty()) {
    	Pos cur = q.poll();// 큐에서 하나 뽑아냄
    	for(int dir = 0;dir<4;dir++) {
    		int nx = cur.x + dx[dir];
    		int ny = cur.y + dy[dir];
    		if(nx < 0 || nx >=n || ny < 0 || ny >= m) continue;
    		if(vis[nx][ny] || board[nx][ny] != 1) continue;
    		vis[nx][ny] = true; // 방문시 true
    		dist[nx][ny] = dist[cur.x][cur.y]+1;
            // [nx][ny]의 경우 [cur.x][cur.y] 보다 한칸 앞에 있으니
            // [cur.x][cur.y] 값에 +1 해준 값이 [nx][ny]의 거리가 됨
    		q.add(new Pos(nx,ny));
    		}
    	}
    	System.out.println(dist[n-1][m-1]);
    }
}

class Pos{
	int x;
	int y;
	
	Pos(int x,int y){
		this.x = x;
		this.y= y;
	}
}