16236번 - 아기 상어

1️⃣ BFS, PriorityQueue

 

✏️ 풀이 과정

문제에서 해결해야 할 부분은 다음에 먹을 물고기를 찾는 것과 물고기를 크기만큼 먹었을 때 상어의 크기를 올려주는 것입니다.

 

먹을 물고기를 찾기 위해서는 두 가지 처리가 필요한데 한 가지는 이동 거리 계산을 위해서 큐 사이즈를 이용하는 BFS를 사용하는 것입니다. 그리고 나머지 한 가지는 거리가 같을 때의 우선 순위를 고려하기 위해서 PriorityQueue를 사용하는 것입니다.(ArrayList에 넣고 정렬하는 것도 상관없습니다.)

 

물고기 한 마리를 먹을 때마다 BFS를 통해 거리마다 탐색하고 가능한 목표가 있을 때 이동 거리를 반환하면서 while문을 돌려야 합니다. 더 이상 먹을 물고기가 없는 경우에 -1 등의 표시를 반환하여 로직을 종료하면 문제가 해결됩니다.

 

크기의 경우 BFS를 완료하고 먹은 물고기를 확정할 때 카운팅하면서 현재 개수가 크기와 같으면 크기를 올려주며 개수를 초기화하면 됩니다. 이 크기와 물고기 크기의 비교를 BFS의 continue 로직에서 수행합니다.

 

⏱ 시간 복잡도

각 BFS는 O(N^2)인데 N^2번 반복될 수 있기 때문에 시간 복잡도는 O(N^4)가 됩니다. N이 20까지 가능하기 때문에 대략 160000번 가량의 계산으로 문제가 해결됩니다.

 

💻 코드

Java

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

public class Main {
	
	static class Point implements Comparable<Point> {
		int r;
		int c;
		
		public Point(int r, int c) {
			this.r = r;
			this.c = c;
		}

		@Override
		public int compareTo(Point o) {
			if(this.r == o.r) {
				return this.c-o.c;
			} else {
				return this.r-o.r;
			}
		}
	}
	
	static int[] dr = {-1, 1, 0, 0};
	static int[] dc = {0, 0, -1, 1};
	static int[][] map;
	
	static int N, curR, curC, curS, curCnt;
	
	static int bfs() {
		LinkedList<Point> q = new LinkedList<>();
		PriorityQueue<Point> pq = new PriorityQueue<>();
		boolean[][] visited = new boolean[N][N];
		q.offer(new Point(curR, curC));
		Point cur;
		int res = 0;
		int time = 0;
		while(!q.isEmpty()) {
			int size = q.size();
			time++;
			for(int i=0;i<size;i++) {
				cur = q.poll();
				for(int j=0;j<4;j++) {
					int nr = cur.r + dr[j];
					int nc = cur.c + dc[j];
					if(nr < 0 || nc < 0 || nr >= N || nc >= N || visited[nr][nc] || map[nr][nc] > curS) {
						continue;
					}
					visited[nr][nc] = true;
					q.offer(new Point(nr, nc));
					if(map[nr][nc] > 0 && map[nr][nc] < curS) {
						pq.offer(new Point(nr, nc));
					}
				}
			}
			if(!pq.isEmpty()) {
				cur = pq.poll();
				curCnt++;
				if(curCnt == curS) {
					curS++;
					curCnt = 0;
				}
				curR = cur.r;
				curC = cur.c;
				res = time;
				map[cur.r][cur.c] = 0;
				break;
			}
		}
		if(res == 0) {
			return -1;
		}
		return res;
	}
	
	public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        map = new int[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) {
					curR = i;
					curC = j;
					map[i][j] = 0;
				}
			}
		}
        int ans = 0;
        int tmp;
        curS = 2;
        curCnt = 0;
        while(true) {
        	tmp = bfs();
        	if(tmp == -1) {
        		break;
        	}
        	ans += tmp;
        }
        System.out.println(ans);
        br.close();
    }
}