백준 17129번 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유 [JAVA]

문제

윌리암슨수액빨이딱따구리 세 식구가 정보섬에 올라왔다!

세 윌리암슨수액빨이딱따구리는 정보섬 2층 어딘가에 모여 앉아 쉬고 있었는데, 저 멀리 청국장과 스시와 맥앤치즈가 있는 것을 발견했다! 아빠는 청국장, 엄마는 스시, 아이는 맥앤치즈가 먹고 싶다. 그래서 이 셋은 현위치로부터 가장 가까운 음식을 먹으러 가기로 했다.

정보섬 2층은 An×m의 격자로 표현된다. 어떤 Ai,j가 0이면 빈 복도여서 지나갈 수 있고, 1이면 장애물로 막혀 지나갈 수 없다. 윌리암슨수액빨이딱따구리 식구는 2, 청국장은 3, 스시는 4, 맥앤치즈는 5이다. 윌리암슨수액빨이딱따구리는 단위 시간마다 한 칸, 상하좌우로 움직일 수 있다. 2, 3, 4, 5는 장애물이 아니므로 지나갈 수 있다. 격자 밖으로는 나갈 수 없으며 시작점으로부터 시작점까지의 거리는 0이다. 시작점은 윌리암슨수액빨리딱따구리의 위치, 즉 2의 위치이다.

과연 윌리암슨수액빨이딱따구리 식구는 어떤 음식에 더 빨리 도착할 수 있을까?

 

 

입력

첫째 줄에 정보섬 2층의 크기 n과 m이 주어진다. (1 ≤ n,m ≤ 3000, 4 ≤ n×m ≤ 9×106)

이후 n행 m열에 걸쳐 0, 1, 2, 3, 4, 5로만 구성된 Ai,j가 주어진다. Ai,j와 Ai,j+1사이에 공백은 주어지지 않는다.

2, 3, 4, 5는 반드시 하나씩 존재하며 2, 3, 4, 5가 아닌 나머지는 0 또는 1이다.

 

 

출력

첫째 줄에 "TAK"(폴란드어로 YES를 의미)을 출력하고, 둘째 줄에 현위치에서 가장 빨리 도착할 수 있는 음식까지의 최단 거리를 출력한다.

아무 음식도 먹을 수 없으면 "NIE"(폴란드어로 NO를 의미)를 출력한다. 이외의 출력은 하지 않는다.

TAK과 NIE를 출력할 때 따옴표는 출력하지 않으며 반드시 대문자로 출력한다.

 

 

예제

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main_BJ_17129_윌리암슨수액빨이딱따구리가정보섬에올라온이유2 {
    
    static class info {
        int x,y,dis;
 
        public info(int x, int y, int dis) {
            this.x = x;
            this.y = y;
            this.dis = dis;
        }
    }
    
    static int n,m, ans;
    static int [][]map;
    static boolean [][] visited;
    static int [] dx = {-1,0,1,0};
    static int [] dy = {0,1,0,-1};
    static PriorityQueue<info> queue = new PriorityQueue<info>(new Comparator<info>() {
 
        @Override
        public int compare(info o1, info o2) {
            // TODO Auto-generated method stub
            return o1.dis-o2.dis;
        }
    });
    
 
    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());
        
        map = new int[n][m];
        visited = new boolean[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)-48;
                if(map[i][j]==2) {
                    queue.offer(new info(i,j,0)); visited[i][j]=true;
                }
            }
        }
        
        bfs();
        System.out.println(ans==0 ? "NIE" : "TAK\n"+ans);
    }
    
    public static void bfs() {
        while(!queue.isEmpty()) {
            
            info info = queue.poll();
            for(int i=0;i<4;i++) {
                int nx = info.x+dx[i];
                int ny = info.y+dy[i];
                
                if(range(nx,ny) && !visited[nx][ny] && map[nx][ny]!=1) {
                    
                    if(map[nx][ny]==0) {
                        visited[nx][ny] = true;
                        queue.offer(new info(nx,ny,info.dis+1));
                    }else {
                        ans = info.dis+1;
                        return;
                    }
                }
            }
        }
    }
    
    public static boolean range(int x, int y) {
        return x>=0 && y>=0 && x<n && y<m;
    }
 
}

 

 

풀이 방법

현재 위치에서 가장 빨리 도착할 수 있는 음식까지의 최단 거리를 구하는 문제였습니다.

딱따구리의 현재 위치 정보를 큐에 넣어주고, 윌리암슨수액빨이딱따구리는 단위 시간마다 상 하 좌 우로 한 칸 이동할 수 있으므로 만약 다음에 갈 곳이 범위 안이고, 방문한 적이 없으며 장애물이 아닌 경우에는 이동할 수 있으므로 다음 칸을 방문했다고 표시해주고 큐에 다음 위치 정보를 넣어주었습니다. 만약 다음 위치가 1이 아니고 0이 아닐 경우 즉, 음식이 있는 경우이기 때문에 현재까지의 이동 거리를 ans 변수에 넣어주고 리턴해 주었습니다.