[백준 - 16236] 골드5 - 아기상어

 

www.acmicpc.net/problem/16236

16236번: 아기 상어

1. 유형

bfs, 시뮬레이션, 우선순위큐

 

2. 풀이

bfs돌릴때마다 잡은 물고기를 우선순위큐에 넣는다.

 

그러고나서 bfs가 끝난 후, poll()을 한 값은 가장 가까우면서, 위에있고, 왼쪽에 있는 물고기이다

 

상어(9)를 찾고나서 맵을 0으로 갱신해주는걸 잊지말자.

 

3. 코드

package 구현.삼성역태;

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

public class back_16236아기상어 {
	static int dr[] = {-1,1,0,0};
	static int dc[] = {0,0,-1,1};
	static class Pair implements Comparable<Pair>{
		int r,c,d;
		public Pair(int r,int c,int d) {
			this.r=r;
			this.c=c;
			this.d=d;
		}
		@Override
		public int compareTo(Pair o) {
			if(this.d==o.d) {
				if(this.r==o.r) {
					return this.c-o.c;					
				}
				return this.r - o.r;
			}
			return this.d - o.d;
		}
		
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int map[][] = new int[n][n];
		Pair shark=null;
		int mysize=2;
		int catchNum=0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				map[i][j] = sc.nextInt();
				if(map[i][j]==9) {
					shark = new Pair(i,j,0);
					map[i][j]=0;
				}
			}
		}
		boolean visit[][];
		int cnt=0;
		while(true) {
			Queue<Pair> q = new LinkedList<>();
			visit = new boolean[n][n];
			q.add(new Pair(shark.r, shark.c, shark.d));
			visit[shark.r][shark.c] = true;
			PriorityQueue<Pair> fish = new PriorityQueue<>();
			while(!q.isEmpty()) {
				Pair cur = q.poll();
				for (int i = 0; i < 4; i++) {
					int nr = cur.r + dr[i];
					int nc = cur.c + dc[i];
					int nd = cur.d + 1;
					//이탈
					if(nr<0 || nr>=n || nc<0 ||nc>=n) continue;
					//나 초과는 못 지나감
					if(map[nr][nc]>mysize) continue;
					//방문한 곳은 안감
					if(visit[nr][nc]) continue;
					visit[nr][nc] = true;
					if(map[nr][nc]!=0 && map[nr][nc] < mysize) {
						fish.add(new Pair(nr, nc, nd));
						continue;
					}
					q.add(new Pair(nr,nc,nd));
				}
			}
			//bfs가 끝나고나서 잡은 것들을 비교한다
			//하나도 못잡으면 종료
			if(!fish.isEmpty()) {
				//잡은 녀석 뽑기
				Pair temp = fish.poll();
				map[temp.r][temp.c] = 0;
				cnt+=temp.d;
				catchNum++;
				if(catchNum == mysize) {
					catchNum=0;
					mysize++;
				}
				//상어위치 갱신
				shark.r=temp.r;
				shark.c=temp.c;
			}else {
				break;
			}
		}//반복끝
		System.out.println(cnt);
	}
}

 

우선순위 큐 부분

static class Pair implements Comparable<Pair>{
		int r,c,d;
		public Pair(int r,int c,int d) {
			this.r=r;
			this.c=c;
			this.d=d;
		}
		@Override
		public int compareTo(Pair o) {
			if(this.d==o.d) {
				if(this.r==o.r) {
					return this.c-o.c;					
				}
				return this.r - o.r;
			}
			return this.d - o.d;
		}
		
	}

 

물고기를 잡았을 때, 판단하는 부분

if(!fish.isEmpty()) {
				//잡은 녀석 뽑기
				Pair temp = fish.poll();
				map[temp.r][temp.c] = 0;
				cnt+=temp.d;
				catchNum++;
				if(catchNum == mysize) {
					catchNum=0;
					mysize++;
				}
				//상어위치 갱신
				shark.r=temp.r;
				shark.c=temp.c;
			}else {
				break;
			}