백준 16236번 : 아기 상어

 문제

www.acmicpc.net/problem/16236

16236번: 아기 상어

16236 아기 상어

 

 구현 방법

 물고기까지의 최단 거리를 구해야하므로 bfs를 통해 구현하였습니다.

먼저 조건이 꽤 많아 구현해야할 것을 정리하였습니다.

1. 최단거리에 있는 물고기 구하기

2. 물고기가 있다면 현재까지의 카운팅 한 초 수를 저장해주고 초기화 ( 물고기를 먹은 좌표에서 다시 탐색해야함 )

2-1. 물고기가 한마리라면 해당 물고기가 있는 좌표로 바꿔줌

2-2. 물고기가 여러마리라면 가장 위에 있는 물고기, 그런 물고기가 여러마리라면 가장 왼쪽에 있는 물고기 먹음 -> 우선순위큐로 물고기 큐를 따로 만들어 정렬하며 저장, 우선순위가 큰 물고기가 있는 좌표로 바꿔줌

3. 물고기 잡은 개수 카운팅

4. 물고기 잡은 개수와 현재 크기가 일치하면 크기를 ++

 

처음에 3번에서 많이 헤맸는데 물고기 개수 카운팅 해주고 크기가 올라가면 다시 처음부터 카운팅 해야합니다...

크기가 처음에 2, 2마리 먹으면 크기는 3으로 커지고 한 마리를 더 먹었을 때 3마리, 크기는 3 => 크기 4가 아니라 

2마리 잡고 크기가 커지면 다시 카운팅을 초기화 해주고 추가로 3마리를 더 잡아야 3마리, 크기는 3 => 크기 4가 됩니다.

 

 구현 코드

package BOJ.Gold;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ16236_아기상어 {
	static int[][] map, visit, deltas= {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 상 하 좌 우
	static int N, cnt, totalCnt, sharkS, time, ans, count, sizeC;
	static Queue<shark> queue;
	static PriorityQueue<shark> fish;
	static class shark implements Comparable<shark>{
		int r, c, size;

		public shark(int r, int c) {
			super();
			this.r = r;
			this.c = c;
		}
		
		@Override
		public int compareTo(shark o) {
			if (this.r==o.r) count++; // 높이가 같다면 count++
			if (count == 0) return this.r-o.r; // 높이가 같지 않다면 높이가 제일 작은 값이 우선순위 ( 젤 위쪽 )
			else {
				count = 0;
				return this.c-o.c; // 높이가 같다면 너비가 제일 작은 값이 우선순위 ( 젤 왼쪽 )
			}
		}
		
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		map = new int[N][N];
		visit = new int[N][N];
		queue = new LinkedList<>();
		fish = new PriorityQueue<>();
		sharkS = 2;
		for (int r=0;r<N;r++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int c=0;c<N;c++) {
				map[r][c] = Integer.parseInt(st.nextToken());
				if (map[r][c]==9) {
					queue.offer(new shark(r, c));
					map[r][c]=0;
				}
			}
		}
		// 입력완료
		bfs();
		if (totalCnt==0) System.out.println(0);
		else System.out.println(ans);
	}
	
	static void bfs() {
		while(!queue.isEmpty()) {
			time++;
			int size = queue.size();
			cnt = 0;
			for (int i=0;i<size;i++) {
				shark now = queue.poll();
				visit[now.r][now.c] = 1; 
				for (int d=0;d<4;d++) {
					int nr = now.r+deltas[d][0];
					int nc = now.c+deltas[d][1];
					if (isIn(nr, nc) && map[nr][nc]<=sharkS && visit[nr][nc]==0) {
						if (map[nr][nc]>0 && map[nr][nc]<sharkS) {
							cnt++; // 현재 먹은 물고기 개수
							fish.offer(new shark(nr, nc)); // 물고기 우선순위큐에 저장
						} else queue.offer(new shark(nr, nc));
						visit[nr][nc] = 1;
					}
				}
			}
			if (cnt>0) {
				totalCnt++; // 전체 물고기 개수 카운트, 한마리도 먹은 것이 없다면 0 출력
				ans += time; / 걸린 시간 구하기
				time = 0;
				sizeC++; // 현재까지 먹은 물고기 개수
				if (sizeC==sharkS) {
					sharkS++; // 아기상어 크기와 먹은 물고기 개수가 같으면 크기 1 증가
					sizeC = 0; // 물고기 개수 초기화
				}
				shark now = fish.poll(); // 맨 처음 값이 내가 먹을 물고기
				map[now.r][now.c] = 0; // 내가 먹을 곳 방문체크
				queue = new LinkedList<>(); // 큐 비워주기
				queue.offer(now); // 내가 앞으로 탐색해야할 좌표 -> 내가 먹을 물고기!
				fish = new PriorityQueue<>(); // 물고기 우선순위큐 비워주기
				visit = new int[N][N]; // 방문처리 초기화
			}
		}
	}
	
	static boolean isIn(int nr, int nc) {
		return nr>=0 && nr<N && nc>=0 && nc<N;
	}
}

 

정답!