백준 (BOJ) 16236 아기 상어

백준 (BOJ) 16236 아기 상어

* 문제 풀이하시는 데에 참고하지 않길 당부드립니다. 전역 static 폭주

풀다가 테스트케이스에서 여러 번 막힌 덕분에 약간의 분노를 느껴 복습을 위해 남기는 상당히 주관적인 포스트이다.

항상 구현/시뮬레이션 문제 풀면 조건 확실히 숙지하고 가자.

아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고,

나머지 칸은 모두 지나갈 수 있다.

따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.

아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다.

아기 상어는 자신의 크기와 같은 수(2렙이면 2마리, 3렙이면 3마리)의 물고기를 먹을 때 마다 크기가 1 증가한다.

테케 3번 진행 이미지)

위의 이미지는 잘못되었다. 처음 1을 섭취한 후 3을 지나 저렇게 갈 수 없다.

해당 시점에 아기 상어의 크기는 2이기 때문이다. 자신 보다 큰 3을 지날 수 없다.

처음 조건을 잘못 이해해서 저기서 꽤 고생했다. 반면교사하자.

1. q만 쓰면 될 것 같았는데 결국 pq도 썼다.

먼저 q로 탐색 범위를 훑고,

다음 pq는 해당 phase에서 먹을 수 있는 물고기들이 나왔을 때 다음의 우선 순위

① 최단 거리

② 보다 높은 위치

③ 보다 왼쪽 위치

를 만족시켜서, 먹을 수 있는 물고기의 위치를 넣으면 알아서 정렬시켜준다.

그리고 조건을 만족시키는 도착 지점의 위치를 함수의 끝에서 뱉어준다(poll).

물론 다 q로 다 훑었는데도 찾지 못했다면, boolean check가 false로 나타나 끝에서 잘못된 place를 뱉는다.

(이 부분은 bfs 메서드의 return 타입을 boolean으로 맞춰서 더 최적화할 수 있을 거 같다.)

잘못된 place를 받은 main에서 판단하여, 엄마 상어를 부를 것인지를 정한다. (boolean flag가 체크 후 루프 종료)

그리고 q, pq와 visited는 매번 시작지점으로부터 진행될 때마다 bfs에서 새로 할당된다.

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; // ***** 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, // 나머지 칸은 모두 지나갈 수 있다. // 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. // 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다. // ** 아기 상어는 자신의 크기와 같은 수(2렙이면 2마리, 3렙이면 3마리)의 물고기를 먹을 때 마다 크기가 1 증가한다. class place implements Comparable{ int x, y, count; place(int x, int y, int count){ this.x = x; this.y = y; this.count = count; } @Override public int compareTo(place p){ // 우선 순위 1: 이동 거리 if(this.count > p.count){ // 새로 들어오는 p가 짧다면, 1 return return 1; }else{ // 우선 순위 2: 높이 if(this.y > p.y) return 1; // 앞에 위치 else if(this.y == p.y){ // 높이가 같다면, 우선 순위 3: 왼쪽 if(this.x > p.x) return 1; else return -1; } else return -1; // 뒤에 위치 } } } public class Main { static int[][] map; static int N; static int[] dx = {0,-1,0,1}; static int[] dy = {-1,0,1,0}; static boolean[][] visited; static int level; // 현재 아기 상어의 크기(level) static int needed; // 다음 레벨로 가기 위해 요구되는 상어 수 static PriorityQueue pq; // 해당 phase 에서 "최단 거리, 더 높은, 왼쪽"을 기준으로 정렬된 pq static Queue q; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); N = Integer.parseInt(br.readLine()); map = new int[N][N]; int x = 0, y = 0; // the current place of a baby shark. StringTokenizer st; for(int i=0; i(); pq = new PriorityQueue<>(); q.add(new place(x, y, count)); visited[y][x] = true; boolean check = false; // 먹을 거 있나 체크 while (!q.isEmpty()){ place p = q.poll(); int px = p.x; int py = p.y; int pCount = p.count+1; // 미리 한 칸 이동할 거 생각해서 더해놓기 for(int i=0; i<4; ++i){ int nx = px + dx[i]; int ny = py + dy[i]; if(nx >= 0 && nx < N && ny >= 0 && ny < N){ if(!visited[ny][nx] && map[ny][nx] <= level){ // 지나갈 수 있는 곳이므로, 일단 방문체크 visited[ny][nx] = true; // 빈 공간이 아니고, 현재 아기상어 레벨 보다 낮으면 '먹음' if(map[ny][nx] < level && 0 < map[ny][nx]){ check = true; //** '먹을 것 있나' 체크 // 일단 후보군 중 하나는 넣고보자. pq.add(new place(nx, ny, pCount)); }else{ // 먹이가 아닌 곳을 지난다면, if(!check) { q.add(new place(nx, ny, pCount)); } } } } } } if(check){ // 먹을 것 찾았으니까, 요구되는 '먹이' 감소 --needed; // 필요한 만큼 먹어치웠다면: level up, needed 갱신 if(needed == 0){ ++level; needed = level; }// else 생략: 먹긴 먹었는데 아직 덜 먹었다면, pass return pq.poll(); } else{ return new place(-1, -1, -1); } } }

from http://verycrazy.tistory.com/35 by ccl(A) rewrite - 2021-12-12 06:02:10