[BJ16236] 아기 상어
✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/백준 알고리즘

[BJ16236] 아기 상어

 백준 - 아기 상어 

문제 링크

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

 

16236번: 아기 상어

N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가

www.acmicpc.net

 

문제 입출력

6
1 1 1 1 1 1
2 2 6 2 2 3
2 2 5 2 2 3
2 2 2 4 6 3
0 0 0 0 0 6
0 0 0 0 0 9
39

 

문제 풀이

더보기

잘못된 풀이

package problem.BJ;


import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;


public class BJ16236_아기상어 {
	static int ans, N, minDis;
	static int sy, sx, eatCnt, sizeCnt = 2;
	static boolean flag;
	static int[][] map;
	static boolean[][] visit;

	// 상하좌우
	static int[] dy = { -1, 1, 0, 0 };
	static int[] dx = { 0, 0, -1, 1 };

	static List<Fish> fishes = new ArrayList<Fish>();


	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());

		map = new int[N][N];
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				int m = map[i][j] = Integer.parseInt(st.nextToken());
				if (1 <= m && m <= 6) fishes.add(new Fish(i, j, m, 0));
				else if (m == 9) {
					sy = i;
					sx = j;
				}
			}

		}

		// 물고기들 거리 초기화
		distanceFish();
		Collections.sort(fishes, Collections.reverseOrder());

		while (true) {
			int prevEatCnt = eatCnt;

			distanceFish();
			Collections.sort(fishes, Collections.reverseOrder());

			eatFish();

			if (prevEatCnt == eatCnt) break;
		}

		// 출력
		System.out.println(ans);

	} // end main


	// 아기 상어가 물고기 먹으러 가는 함수
	private static void eatFish() {
		for (int f = fishes.size() - 1; f >= 0; f--) {
			Fish fish = fishes.get(f);

			if (fish.size < sizeCnt) {
				int fy = fish.y;
				int fx = fish.x;

				minDis = Integer.MAX_VALUE;
				visit = new boolean[N][N];
				Queue<Shark> sq = new ArrayDeque<>();
				sq.offer(new Shark(sy, sx, 0));
				visit[sy][sx] = true;

				// 상어가 물고기 위치로 먹으러 간다.
				while (!sq.isEmpty()) {
					int size = sq.size();

					for (int i = 0; i < size; i++) {
						Shark shark = sq.poll();
						int y = shark.y;
						int x = shark.x;

						for (int d = 0; d < 4; d++) {
							int ny = y + dy[d];
							int nx = x + dx[d];

							if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
							if (visit[ny][nx]) continue;
							if (map[ny][nx] > sizeCnt) continue;

							// 해당 물고기를 먹었다면
							if (ny == fy && nx == fx) {
								eatCnt++;
								fishes.remove(f);
								minDis = Math.min(minDis, shark.d + 1);
								ans += minDis;
								sy = ny;
								sx = nx;

								if (eatCnt == sizeCnt) {
									sizeCnt++;
									eatCnt = 0;
								}

								return;
							}

							sq.offer(new Shark(ny, nx, shark.d + 1));
							visit[ny][nx] = true;
							sy = ny;
							sx = nx;

						}

					}

				}

			}

		}

	} // end eatFish


	// 물고기들과의 거리를 재는 함수
	private static void distanceFish() {
		for (Fish fish : fishes) fish.dis = extent(sy, sx, fish.y, fish.x);
	} // end distanceFish


	// 맨하튼 거리 재는 함수
	private static int extent(int y1, int x1, int y2, int x2) {
		return Math.abs(y1 - y2) + Math.abs(x1 - x2);
	} // end extent


	static class Fish implements Comparable<Fish> {
		int y, x;
		int size; // 물고기의 크기
		int dis; // distance


		public Fish(int y, int x, int size, int dis) {
			super();
			this.y = y;
			this.x = x;
			this.size = size;
			this.dis = dis;
		}


		@Override
		public String toString() {
			return "Fish [y=" + y + ", x=" + x + ", size=" + size + ", dis=" + dis + "]";
		}


		@Override
		public int compareTo(Fish o) {
			return (this.dis == o.dis ? (this.y == o.y ? this.x - o.x : this.y - o.y)
			    : this.dis - o.dis);
		}

	} // end Fish


	static class Shark {
		int y, x;
		int d; // depth


		public Shark(int y, int x, int d) {
			super();
			this.y = y;
			this.x = x;
			this.d = d;
		}


		@Override
		public String toString() {
			return "Shark [y=" + y + ", x=" + x + ", d=" + d + "]";
		}

	} // end Shark
}

Fish List 를 만들었다. 그리고 나서 거리, y, x 순으로 정렬을 해줘서 하나씩 빼고 remove 하며 fish 를 먹으려고 했는데..

한가지 간과한 점이 있었다. 바로 상어가 지나가는 칸에서 바로 물고기를 먹을 수 있다는 것..

예제 6번에서 보면

(0, 5)의 물고기를 먹으러 갈 때 상어는 돌아서 간다.

그 돌아서 갈 때 지나가는 칸의 물고기를 다 먹을 수 있게 된다. 하지만 나는 리스트를 사용하므로 이렇게 되면 해당 칸의 물고기를 remove 할 수 없게 된다..

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;


public class Main {
	static int ans, N;
	static int sy, sx, sSize = 2, sEatCnt;
	static int[][] map;
	static boolean[][] visit;

	// 상하좌우
	static int[] dy = { -1, 1, 0, 0 };
	static int[] dx = { 0, 0, -1, 1 };

	static Queue<Node> q = new ArrayDeque<>();


	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());

		map = new int[N][N];
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				int m = map[i][j] = Integer.parseInt(st.nextToken());
				if (m == 9) {
					sy = i;
					sx = j;
				}

			}

			// System.out.println(Arrays.toString(map[i]));

		}

		// 시뮬레이션
		while (true) {
			int cnt = bfs();
			ans += cnt;

			if (cnt == 0) break; // 더이상 먹을 물고기가 없다면
		}

		// 출력
		System.out.println(ans);

	} // end main


	private static int bfs() {
		int minY = Integer.MAX_VALUE;
		int minX = Integer.MAX_VALUE;
		int minDis = Integer.MAX_VALUE;

		// 초기화
		Queue<Node> q = new ArrayDeque<>();
		visit = new boolean[N][N];

		visit[sy][sx] = true;
		q.offer(new Node(sy, sx, 0));

		while (!q.isEmpty()) {
			Node node = q.poll();
			int y = node.y;
			int x = node.x;

			// 상하좌우 탐색
			for (int d = 0; d < 4; d++) {
				int ny = y + dy[d];
				int nx = x + dx[d];

				if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
				if (visit[ny][nx]) continue;
				if (map[ny][nx] > sSize) continue;

				// 만약 물고기고 먹을 수 있다면 다음과 같은 우선순위를 따른다.
				// 1. 거리가 가장 가까운 물고기
				// 2. 가장 위에 있는 물고기
				// 3. 가장 왼쪽에 있는 물고기
				if (map[ny][nx] != 0 && map[ny][nx] < sSize) {
					if (node.d + 1 < minDis) {
						minY = ny;
						minX = nx;
						minDis = node.d + 1;
					} else if (node.d + 1 == minDis) {
						if (ny < minY) {
							minY = ny;
							minX = nx;
							minDis = node.d + 1;
						} else if (ny == minY) {
							if (nx < minX) {
								minY = ny;
								minX = nx;
								minDis = node.d + 1;
							}

						}

					}

				}

				visit[ny][nx] = true;
				q.offer(new Node(ny, nx, node.d + 1));
			}

		}

		// 물고기를 먹었는지 아닌지 체크
		if (minDis == Integer.MAX_VALUE) return 0;

		sEatCnt++;

		if (sEatCnt == sSize) {
			sSize++;
			sEatCnt = 0;
		}

		map[minY][minX] = 0;
		map[sy][sx] = 0;

		sy = minY;
		sx = minX;

		return minDis;

	} // end bfs


	// 맨하튼 거리 재는 함수
	private static int extent(int y1, int x1, int y2, int x2) {
		return Math.abs(y1 - y2) + Math.abs(x1 - x2);
	} // end extent


	static class Node {
		int y, x;
		int d;


		public Node(int y, int x, int d) {
			super();
			this.y = y;
			this.x = x;
			this.d = d;
		}

	} // end Node
}
  • bfs 를 이용하여 풀 수 있다.
  • 우선순위 조건을 둘 수 있다면 풀 수 있는 문제 였다.

 

 

 

 

 

 

 

 

 

 

# 백준 아기상어 bfs # BJ 아기 상어 # 백준 아기 상어 # 백준 아기상어 java

 

728x90
저작자표시 비영리 변경금지

'✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺 > 백준 알고리즘' 카테고리의 다른 글

[BJ1062] 가르침  (0) 2022.11.06
[BJ15684] 사다리 조작  (0) 2022.11.05
[BJ3055] 탈출  (1) 2022.10.10
[BJ10026] 적록색약  (0) 2022.10.10
[BJ13023] ABCDE  (0) 2022.10.02

    티스토리툴바