[BOJ] 16236. 아기 상어

BFS를 이용한 문제이다.

이 문제에선 다음에 갈 점들의 우선순의가 거리>위쪽>왼쪽 으로 주어져있으므로 다음에 갈점을 위해 PriorityQueue를 사용하였다. BFS를 한번 돌때마다 pq에 갈점들을 쭉저장하고 pq가 없다면 멈추는 형식으로 구현하였다.

문제를 이해하는데 오래걸렸다. 문제를 꼼꼼히 읽는 습관이 필요할 것 같다.

package boj2;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main_bj_16236_아기상어 {
    static int[] di= {-1,0,1,0};
    static int[] dj= {0,1,0,-1};
    
    static int[][] map;
    static boolean[][] visit;
 
    static Queue<Pos> queue;
    static PriorityQueue<Pos> pq;
    
    static int curSize;
    static int stackSize;
    static int N;
    static int answer;
    static int startI;
    static int startJ;
    
    static class Pos implements Comparable<Pos>{
        int i,j,distance;
        Pos(int i,int j,int d){
            this.i=i;this.j=j;distance=d;
        }
        @Override
        public int compareTo(Pos o) {
            if(distance==o.distance) {
                if(i==o.i)
                    return Integer.compare(j, o.j);
                return Integer.compare(i, o.i);
            }
            return Integer.compare(distance, o.distance);
        }
    }
    
    
    
    public static void main(String[] args) throws Exception {
        BufferedReader br=  new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        N=Integer.parseInt(br.readLine());
        map=new int[N][N];
        visit=new boolean[N][N];
        
        for(int i=0;i<N;i++) {
            st=new StringTokenizer(br.readLine());
            for(int j=0;j<N;j++) {
                map[i][j]=Integer.parseInt(st.nextToken());
                if(map[i][j]==9) {
                    startI=i;startJ=j;
                }
            }
        }
        
        curSize=2;
        stackSize=0;
        answer=0;
        
        queue=new LinkedList<>();
        while(true) {
            visit=new boolean[N][N];
            pq=new PriorityQueue<>();
            
            bfs();
            
            if(pq.size()==0) {
                break;
            }else {
                Pos togo=pq.poll();
                
                answer+=togo.distance;
                map[startI][startJ]=0;
                startI=togo.i;
                startJ=togo.j;
                stackSize+=1;
                if(stackSize==curSize) {
                    stackSize=0;
                    curSize+=1;
                }
            }
        }
        System.out.println(answer);
        
    }
    static void bfs() {
        queue.offer(new Pos(startI, startJ, 0));
        visit[startI][startJ]=true;
        
        while(!queue.isEmpty()) {
            Pos cur = queue.poll();
            
            for(int dir=0;dir<4;dir++) {
                int nextI=cur.i+di[dir];
                int nextJ=cur.j+dj[dir];
                
                if(nextI<0 ||nextI>=N || nextJ<0 ||nextJ>=N)
                    continue;
                
                if((map[nextI][nextJ]==0 || map[nextI][nextJ]==curSize) && visit[nextI][nextJ]==false) {
                    visit[nextI][nextJ]=true;
                    queue.offer(new Pos(nextI, nextJ, cur.distance+1));
                }
                
                if(0<map[nextI][nextJ]&& map[nextI][nextJ]<curSize && visit[nextI][nextJ]==false) {
                    pq.offer(new Pos(nextI, nextJ, cur.distance+1));
                }
            }
            
        }
    }
}