[BOJ]16236_아기상어(BFS응용)

진짜 과장 거의 안하고, 하루종일 이거만 푼 거 같다.

잘 하는 분들은 한시간만에 풀던데, 난 거의 열배넘는 시간을 들여서 겨우 했다.

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

16236번: 아기 상어

 

처음에 문제를 읽을 때 도저히 감도 잡히지 않았다. 해설을 보고나서야 BFS구나를 깨달은 나는 ㅄ인가.

암튼,해설대로만 하지 않고 그래도 아무것도 안보고 다시 시도해서 겨우겨우 하는 데 성공했다.

단, 중간중간 버그잡는게 두시간가까이 걸렸다.

 

절대 대충 이해하지 말자. 하나하나 따져서 이해해야만 내것이 된다.

 

예를 들어, 79번라인에 visited를 어디서 초기화를 시켜줘야 하는지?(처음시도에는 스태틱변수로 놨다가 낭패를 봤다. 새로운 상어장소에서 주변 자리들을 탐색할 때마다 다시 visited를 초기화 해야 함을 명확하게 알고 있어야 한다. 그냥 대충 외워서 방문체크해야지~이러면 어디서 초기화를 해야 하는지 헷갈리게 되서 실수를 한다)

또한, 처음시작점도 0으로 바꿔줘야 bfs탐색시 그냥 지나가는데 처음의 시작을 고려를 하지 않아 계속 9로 남아서 얘를 피해가느라 답이 다르게 나오기도 하였다.

작지만 절대 사소하지 않은, 용납되지 않는 실수들이다.

 

다음은 코드. Place라는 새로운 클래스를 이용하고, 우선순위큐를 사용한 것이 특징이다. 또한, 일반적인 bfs와 달리, while(!qu.isEmpty())형식으로 탐색을 끝내버리지 않는다. 이 탐색은 그저 가깝고 먹을 수 있는 물고기를 탐색하는 bfs일 뿐이니, 상어가 다시 먹은 물고기자리로 이동해서 또 새로 물고기를 탐색해야 하므로, 젤바깥에 while(true)로 한번 더 감쌌다. 종료되는 조건은 더이상 먹을 수 있는 후보에 드는 물고기가 없을 때일 뿐이다.

package ws0223;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

public class 아기상어 {
	
	static int N;
	static int[][] mat;
	static int[] dr = {-1,0,1,0};
	static int[] dc = {0,1,0,-1};//상우하좌
	static int sharkSize=2;
	static int result, eatCnt;
	
	static class Place{
		int r;
		int c;
		int dist;
		public Place(int r, int c, int dist) {
			super();
			this.r = r;
			this.c = c;
			this.dist = dist;
		}
//		@Override
//		public int compareTo(Place o) {
//			if(this.dist == o.dist) {
//				return (this.r-o.r == 0)? this.c-o.c:this.r-o.r;
//			}
//			return this.dist - o.dist;
//		}
		@Override
		public String toString() {
			return "Place [r=" + r + ", c=" + c + ", dist=" + dist + "]";
		}
		
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in); 
		N = sc.nextInt();
		mat = new int[N][N];
//		visited = new boolean[N][N];
		
		int sharkR=0, sharkC=0;
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				mat[i][j] = sc.nextInt();
				if(mat[i][j]==9) {
					sharkR = i;
					sharkC = j;
				}
			}
		}
		mat[sharkR][sharkC] = 0;//처음에 이거 안넣어서 디버깅 1시간넘게 함..
		bfs(sharkR, sharkC);
		System.out.println(result);
	}	
	
	static void bfs(int r, int c) {
		Queue<Place> sharkPlaceQ = new LinkedList<Place>(); 
		Place shark = new Place(r,c,0);
		sharkPlaceQ.offer(shark);
		
		PriorityQueue<Place> fishQu = new PriorityQueue<>(new Comparator<Place>() {
			@Override
			public int compare(Place o1, Place o2) {
				if(o1.dist == o2.dist) {
					return (o1.r==o2.r)? o1.c-o2.c:o1.r-o2.r;
				}
				return o1.dist - o2.dist;
			}
		});
		
		while(true) {
			boolean[][] visited = new boolean[N][N];
			while(!sharkPlaceQ.isEmpty()) {
				Place current = sharkPlaceQ.poll();
				
				visited[current.r][current.c] = true;
				
				//bfs로 물고기들 거리를 구하면서 우선순위큐에 넣기
				for(int i=0; i<4; i++) {
					int nr = current.r + dr[i];
					int nc = current.c + dc[i];
					
					if(nr>=0 && nr<N && nc>=0 && nc<N && !visited[nr][nc]) {
						if(mat[nr][nc] == 0) {
							sharkPlaceQ.offer(new Place(nr,nc,current.dist+1));
							visited[nr][nc] = true;
						}
						else {
							if(mat[nr][nc] < sharkSize ) {
								visited[nr][nc] = true;
								sharkPlaceQ.offer(new Place(nr,nc,current.dist+1));
								fishQu.offer(new Place(nr,nc,current.dist+1));
							}
							else if(mat[nr][nc] == sharkSize) {
								visited[nr][nc] = true;
								sharkPlaceQ.offer(new Place(nr,nc,current.dist+1));
							}
						}
					}
				}
			}
			//선정된 물고기 먹으러 이동
			if(!fishQu.isEmpty()) {
				if(++eatCnt == sharkSize) {
					sharkSize++;
					eatCnt = 0;
				}	
//				System.out.println(fishQu);
				Place nextSharkPlace = fishQu.poll();
//				System.out.println("상어이동장소: "+nextSharkPlace.r+", "+nextSharkPlace.c);
				mat[nextSharkPlace.r][nextSharkPlace.c] = 0;
				fishQu.clear();
							
				result+=nextSharkPlace.dist;
				sharkPlaceQ.offer(new Place(nextSharkPlace.r, nextSharkPlace.c, 0));
			}else {
				return;
			}	
		}	
	}
}