BOJ16236.아기 상어

Seoyeon Kim·2026년 4월 9일
Gold3Javaalgorithmboj백준알고리즘자바

Coding

목록 보기
8/11

BOJ 16236.아기상어 링크

문제

지문

N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.
아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.
아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.

아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.

  • 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다
  • 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
  • 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
    - 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
    - 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

아기 상어의 이동은 1초 걸리고, 물고기를 먹는데 걸리는 시간은 없다고 가정한다. 즉, 아기 상어가 먹을 수 있는 물고기가 있는 칸으로 이동했다면, 이동과 동시에 물고기를 먹는다.
물고기를 먹으면, 그 칸은 빈 칸이 된다.

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

공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 공간의 크기 N(2 ≤ N ≤ 20)이 주어진다.
둘째 줄부터 N개의 줄에 공간의 상태가 주어진다. 공간의 상태는 0, 1, 2, 3, 4, 5, 6, 9로 이루어져 있고, 아래와 같은 의미를 가진다.
0: 빈 칸
1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
9: 아기 상어의 위치
아기 상어는 공간에 한 마리 있다.

출력

첫째 줄에 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다.

입출력 예시

[예시 1]
입력
3
0 0 1
0 0 0
0 9 0
.
출력
3

[예시 2]
입력
4
4 3 2 1
0 0 0 0
0 0 9 0
1 2 3 4
.
출력
14

문제 정리

[목표]
N*N 배열 내부에서 델타배열로 이동하고,
일정 조건에 따라 해당 칸에 이동할 때,
더 이상 조건을 만족할 수 없는 총 시간
.
[종료 조건]

  • 더 이상 먹을 수 있는 물고기가 없을 때.
    즉,
    1. 남아있는 물고기가 0마리
    1. 남아있는 물고기가 모두 상어보다 클 때
      .

[조건]

  • 상어 이동
    • 상하좌우 1칸씩 이동 = 1초
    • 물고기 먹는 데 시간 0초 = 이동과 동시에 먹음
  • 이동 가능 조건
    • 자신보다 큰 물고기(큰 자연수) : 지날 수 없음
    • 자신과 같은 크기 물고기 : 지날 수 있음. 그러나 먹지 못함
    • 자신보다 작은 물고기 : 지날 수 있음. 먹을 수 있음
    • 빈 칸 : 자유롭게 이동
  • 먹을 물고기 선택 조건 = 해당 라운드 목표 지점
    • 먹을 수 있는 물고기가 1마리 = 목표 설정
    • 먹을 수 있는 물고기가 N마리 = 가까운 물고기 선택
      • 거리가 같은 물고기가 N마리 : 가장 위쪽 먼저
        - 거리가 같고, 행이 같다면 왼쪽 선택
  • 거리 측정
    • 거리 = 아기 상어 위치 ~ 물고기 위치까지 지나야 하는 칸 수의 최솟값
    • 이 때, 자신보다 큰 값의 칸은 지날 수 없음
      • => 항상 업데이트 필요
  • 성장 조건
    • 내 크기 = 먹은 물고기 수 => 크기 1 증가
      • 물고기 크기는 먹을수 있는지 유무를 따지는 것에만 사용
    • 크기 증가할 때, 먹을 수 있는 물고기가 달라짐

아이디어

변수 설정

//기본적인 변수
	static int sharkR;
	static int sharkC; // 상어 현재 위치 저장
	static int sharkSize = 2; // 상어 현재 크기(초기 2)
	static int eatNow = 0; // 현재 먹은 물고기 수(초기 0)
	static int time = 0; //소요 시간. 출력 값
    static int[][] map; //N*N 2차원 배열 맵
    .
    private static class Fish {
		int fishR, fishC, dist;
		public Fish(int fishR, int fishC, int dist) {
			this.fishR = fishR;
			this.fishC = fishC;
			this.dist = dist;
		}
	} //물고기 위치, 상어로부터 거리 저장 클래스
    .
    static int[] dr = { -1, 0, 0, 1 };
	static int[] dc = { 0, -1, 1, 0 };
    // 델타배열. 이 때, 위 -> 왼쪽 순으로 조회하므로 상좌우하 순서

로직

  • 현재 상어 위치에서 먹을 수 있는 최우선 물고기 찾기
    • 이동 가능한 위치 탐색
      • 델타배열로 움직일 수 있음
        • BFS 이용하여 이동
    • 물고기 탐색
      • 물고기 크기, 현재 상어 크기 비교
        • 우선순위에 따라 정렬
          • 가장 가까운 거리부터
          • 같은 거리라면 위->왼쪽 우선순위 적용

위 순서 반복하면서 물고기 먹을 수 없으면 종료

코드

전체 코드

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

public class BOJ_16236_2 {
	static int sharkR;
	static int sharkC; // 상어 위치
	static int sharkSize = 2; // 상어 현재 크기
	static int eatNow = 0; // 현재 먹은 물고기 수
	static int time = 0;

	static int[][] map;


	private static class Fish {
		int fishR, fishC, dist; //물고기 위치 fishR,fishC, 상어로부터 거리 dist

		public Fish(int fishR, int fishC, int dist) {
			this.fishR = fishR;
			this.fishC = fishC;
			this.dist = dist;
		}

	}

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

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

		int n = Integer.parseInt(st.nextToken());

		map = new int[n][n];

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < n; j++) {
				int temp = Integer.parseInt(st.nextToken());
				map[i][j] = temp;
				if (temp == 9) { //맵 채워넣으며 상어 초기 위치 저장
					sharkR = i;
					sharkC = j; // 상어 위치 저장
					map[i][j] = 0;
				}
			}
		} // 입력 끝

		while (true) {
			Fish target = bfs(n); // 조건에 맞는 가장 최우선 물고기 저장

			if (target == null) //타겟이 없다면 == 먹을 수 있는 물고기 없다면 종료
				break;

			sharkR = target.fishR;
			sharkC = target.fishC; //현재 상어 위치 목표 물고기 위치로 변경
			map[sharkR][sharkC] = 0; //기존 상어 위치 0으로 초기화
			time += target.dist; //이동 거리만큼 시간 증가
			eatNow++; //물고기 1마리 먹음

			if (eatNow == sharkSize) { //현재 먹은 물고기 개수 == 상어 크기라면, 상어 크기 변경
				sharkSize++; //상어 크기 ++
				eatNow = 0; //먹은 물고기 개수 초기화
			}
		}

		System.out.println(time);

	}

	private static Fish bfs(int n) { // 각 물고기까지 최단 이동 거리 -> BFS
		boolean[][] visited = new boolean[n][n]; //BFS 위한 방문 배열
		Queue<int[]> q = new ArrayDeque<>(); //BFS 위한 큐 생성


		PriorityQueue<Fish> pq = new PriorityQueue<>(new Comparator<Fish>() {
			//먹을 수 있는 물고기 후보 비교, 저장하는 우선순위 큐

			@Override
			public int compare(Fish o1, Fish o2) { //물고기 비교
				if (o1.dist != o2.dist) //물고기~상어 거리가 같지 않다면
					return o1.dist - o2.dist; //짧은 쪽 리턴
				else { //물고기~상어 거리가 같다면
					if (o1.fishR != o2.fishR) //행이 같다면
						return o1.fishR - o2.fishR; //위쪽에 있는 것 꺼냄
					else
						return o1.fishC - o2.fishC; //왼쪽에 있는 것 꺼냄
				}
			}

		});

		q.offer(new int[] { sharkR, sharkC, 0 }); //기초 위치 = 상어 위치 큐에 저장. 이 때, 본인 위치이므로 거리=0
		visited[sharkR][sharkC] = true; //방문 처리

		int minDist = Integer.MAX_VALUE; //최단 거리 비교 위한 임시 배열

		while (!q.isEmpty()) { //BFS 진행. = 상어 위치에 대한 큐. 더 이상 조회할 것이 없을 때까지 반복
			int[] curr = q.poll();

			int r = curr[0];
			int c = curr[1];
			int dist = curr[2]; //거리

			if (dist > minDist) //현재 조회 물고기~상어 거리> 현재 최소 물고기~상어 거리 라면, 먹지 않을 것. continue
				continue;

			for (int d = 0; d < 4; d++) { //델타배열 돌아!
				int nr = r + dr[d];
				int nc = c + dc[d];

				if (nr < 0 || nr >= n || nc < 0 || nc >= n) //범위 체크 continue
					continue;
				if (visited[nr][nc]) //방문 체크 continue
					continue;

				if (map[nr][nc] > sharkSize) //물고기가 현재 상어 크기보다 크다면 continue
					continue;

				visited[nr][nc] = true; //방문처리
				int nextDist = dist + 1; //거리+1

				if (map[nr][nc] > 0 && map[nr][nc] < sharkSize) { //값이 0보다 크고, 상어 크기보다 작다면 먹을 수 있음
					pq.offer(new Fish(nr, nc, nextDist)); //우선순위큐에 넣음
					minDist = nextDist; //최솟값 갱신
				}

				q.offer(new int[] { nr, nc, nextDist }); //이동할 수 있다면 큐 추가
			}
		}

		if (pq.isEmpty()) //물고기 후보가 아무도 없다면 null 반환
			return null;
		return pq.poll(); //우선순위큐에서 하나만 뽑음 = 가장 최선의 물고기 반환

	}

}

상세 코드

물고기 탐색 후 상어 이동

while (true) {
			Fish target = bfs(n); // 조건에 맞는 가장 최우선 물고기 저장

			if (target == null) //타겟이 없다면 == 먹을 수 있는 물고기 없다면 종료
				break;

			sharkR = target.fishR;
			sharkC = target.fishC; //현재 상어 위치 목표 물고기 위치로 변경
			map[sharkR][sharkC] = 0; //기존 상어 위치 0으로 초기화
			time += target.dist; //이동 거리만큼 시간 증가
			eatNow++; //물고기 1마리 먹음

			if (eatNow == sharkSize) { //현재 먹은 물고기 개수 == 상어 크기라면, 상어 크기 변경
				sharkSize++; //상어 크기 ++
				eatNow = 0; //먹은 물고기 개수 초기화
			}
		}

먹을 수 있는 물고기 탐색 후 출력

private static Fish bfs(int n) { // 각 물고기까지 최단 이동 거리 -> BFS
		boolean[][] visited = new boolean[n][n]; //BFS 위한 방문 배열
		Queue<int[]> q = new ArrayDeque<>(); //BFS 위한 큐 생성


		PriorityQueue<Fish> pq = new PriorityQueue<>(new Comparator<Fish>() {
			//먹을 수 있는 물고기 후보 비교, 저장하는 우선순위 큐

			@Override
			public int compare(Fish o1, Fish o2) { //물고기 비교
				if (o1.dist != o2.dist) //물고기~상어 거리가 같지 않다면
					return o1.dist - o2.dist; //짧은 쪽 리턴
				else { //물고기~상어 거리가 같다면
					if (o1.fishR != o2.fishR) //행이 같다면
						return o1.fishR - o2.fishR; //위쪽에 있는 것 꺼냄
					else
						return o1.fishC - o2.fishC; //왼쪽에 있는 것 꺼냄
				}
			}

		});

		q.offer(new int[] { sharkR, sharkC, 0 }); //기초 위치 = 상어 위치 큐에 저장. 이 때, 본인 위치이므로 거리=0
		visited[sharkR][sharkC] = true; //방문 처리

		int minDist = Integer.MAX_VALUE; //최단 거리 비교 위한 임시 배열

		while (!q.isEmpty()) { //BFS 진행. = 상어 위치에 대한 큐. 더 이상 조회할 것이 없을 때까지 반복
			int[] curr = q.poll();

			int r = curr[0];
			int c = curr[1];
			int dist = curr[2]; //거리

			if (dist > minDist) //현재 조회 물고기~상어 거리> 현재 최소 물고기~상어 거리 라면, 먹지 않을 것. continue
				continue;

			for (int d = 0; d < 4; d++) { //델타배열 돌아!
				int nr = r + dr[d];
				int nc = c + dc[d];

				if (nr < 0 || nr >= n || nc < 0 || nc >= n) //범위 체크 continue
					continue;
				if (visited[nr][nc]) //방문 체크 continue
					continue;

				if (map[nr][nc] > sharkSize) //물고기가 현재 상어 크기보다 크다면 continue
					continue;

				visited[nr][nc] = true; //방문처리
				int nextDist = dist + 1; //거리+1

				if (map[nr][nc] > 0 && map[nr][nc] < sharkSize) { //값이 0보다 크고, 상어 크기보다 작다면 먹을 수 있음
					pq.offer(new Fish(nr, nc, nextDist)); //우선순위큐에 넣음
					minDist = nextDist; //최솟값 갱신
				}

				q.offer(new int[] { nr, nc, nextDist }); //이동할 수 있다면 큐 추가
			}
		}

		if (pq.isEmpty()) //물고기 후보가 아무도 없다면 null 반환
			return null;
		return pq.poll(); //우선순위큐에서 하나만 뽑음 = 가장 최선의 물고기 반환

	}

정리

  • 시뮬레이션을 풀어야 할 것 같아 선택했는데........
  • 시뮬레이션에서 현재 상태 갱신 처리 부분 필요하다. 이를 기반으로 문제가 이어지기 때문에 한 번 꼬이면 디버깅도 어렵다
  • 시뮬레이션 특징 = 조건 많음. 간과하고 무턱대고 풀기 시작했기에 변수, 조건을 계속 추가해가며 n번정도 다시 풀었다.
  • 지문을 보고 냅다 시작하는게 아니라, 필요한 변수와 로직을 잘 구상하는 습관이 필요할 것 같다.
    1. 처음에 상어 위치를 배열로 저장하려고 했는데, 결론적으로 행/열 따로 int형으로 저장해서 쉬운 로직이 되었다.
    1. 상어 위치가 계속 변함에 따라 각 물고기와의 거리도 계속 갱신해야 했다.
      처음에 지문을 제대로 이해하지 못하고 map에서 물고기 위치를 받을 때 List<Fish> FishList 에 모든 물고기의 위치와 크기, 거리를 저장하려고 했다.
      -> 아예 다른 결과 발생.
      계속 거리 갱신이 필요한 해당 문제에서는 각 변수가 어디에 쓰이는지, 어떤 로직이 필요한지 미리 정리하고 들어가야한다.
      => 그런 의미에서 손코딩 습관 들이기.
  • 최단거리 문제에서 이동 비용이 동일하다면 (간선 가중치가 없다면) BFS 적용.
profile
Seoyeon Kim
이전 포스트

BOJ 7569. 토마토

다음 포스트

BOJ20055.컨베이어 벨트 위의 로봇

0개의 댓글