16236 - 아기상어(G3)

문제

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

 

풀이

문제의 핵심은 BFS를 사용하여 가장 가까운 먹이를 찾고 이를 반복하는 것이다.
이 부분에서 문제의 조건인 '먹을 수 있는 물고기가 1마리보다 많다면' 의 조건을 올바르게 구현하는데 많은 시간이 들었다.

첫 번째는 단순히 BFS의 사방 탐색 방향을 조건과 같이 위쪽 / 왼쪽 / 오른쪽 / 아래로 설정했으나, 이러한 방법이 문제가 있다는 사실을 파악하였다.
두 번째로 조건에 맞는 값들을 완전 탐색으로 전부 포집 후, 이를 소팅하려 했으나 의미없는 반복문이 너무 늘어나고 방향성을 수정하게 되었다.

bfs문을 돌리면서 상어가 먹을 수 있는 조건의 먹이들을 확인하고 이를 우선순위 큐에 집어넣어 정렬한 뒤 최소값을 찾는 방법을 생각해보았다.

이를 위해 bfs 메서드에서 돌아가는 q와, 우선순위 큐인 fish를 분리한다. 이후 조건(더 이상 탐색할 수 있는 먹이가 없음)에 맞을 때까지 while문을 돌려 값을 갱신한다.

소스 코드는 아래와 같다.

소스 코드

import java.util.*;
import java.io.*;

public class Main {
	static int N, res = 0;
	static int[][] map;
	static boolean[][] visit;
	static Shark baby = new Shark(-1, -1, 2, 0); //상어 설정
	static Queue<int[]> q = new ArrayDeque<>(); // R / C / 시간
	static PriorityQueue<int[]> fish = new PriorityQueue<>(new Comparator<int[]>() {
		@Override
		public int compare(int[] o1, int[] o2) {
			if(o1[2] == o2[2]) {
				if(o1[0] == o2[0]) {
					return o1[1] - o2[1]; //가장 왼쪽에 있는 물고기
				}
				return o1[0] - o2[0]; //가장 위에 있는 물고기
			}
			return o1[2] - o2[2]; //가장 가까운 물고기
		}
		
	});
	
	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 boolean[N][N];
		
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if(map[i][j] == 9) {
					baby.r = i;
					baby.c = j;
					map[i][j] = 0; //초기화
				}
			}
		}
		
		while(true) {
		bfs();	//먹이 탐색
		if(fish.size() == 0) break; //기저조건 : 상어가 먹을 수 있는 먹이가 없음
		
		int temp[] = fish.poll(); 	//먹을 물고기 저장한 값 (R, C, Time)
		
		res += temp[2]; //시간 저장
		baby.r = temp[0];
		baby.c = temp[1]; //좌표 갱신
		baby.eat();
		
		map[baby.r][baby.c] = 0; 	//자리 초기화
		q.clear(); 				   	//큐 초기화
		fish.clear();				//
		visit = new boolean[N][N]; 	//방문 초기화
		
		}
		
		System.out.println(res);
	}
	
	static void bfs() {
		q.offer(new int[] {baby.r, baby.c, 0}); //상어가 가까운 먹이를 탐색
		
		while(!q.isEmpty()) {
			int[][] shift = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}}; //U L R D
			int temp[] = q.poll(); //임시 값 빼오기
			int r = temp[0];
			int c = temp[1];
			int time = temp[2];
			
			//조건 : 작은 물고기를 발견했을 경우 fish Queue에 추가
			if (map[r][c] != 0 && baby.size > map[r][c]) {
				fish.offer(new int[] {r, c, time});
			}
			
			for (int i = 0; i < shift.length; i++) {
				int nr = r + shift[i][0];
				int nc = c + shift[i][1];
				
				if(nr < 0 || nc < 0 || nr >= N || nc >= N || visit[nr][nc] || map[nr][nc] > baby.size) continue;
				visit[nr][nc] = true; //방문 처리
				q.offer(new int[] {nr, nc, time + 1});
			}
		}
	}
	
	static class Shark {
		int r, c; //좌표
		int size, eat; //크기, 현재 먹은 횟수
		
		public Shark(int r, int c, int size, int eat) {
			this.r = r;
			this.c = c;
			this.size = size;
			this.eat = eat;
		}
		
		void eat() {
			eat += 1;
			if (size == eat) {
				eat = 0;
				size += 1;
			}
		}
	}
}