close
프로필 배경
프로필 로고

JinHxxxxKim

알고리즘 · 2024. 2. 27. fullscreen 넓게보기

[BOJ] - 아기 상어 / 16236번 (Java)

[BOJ] - 아기 상어 / 16236번 (Java)

[BOJ] - 아기 상어 / 16236번 (Java)

1. 문제 접근

문제를 요약하면, 아기 상어가 먹을 수 있는 먹이를 모두 먹는데 이동한 거리는 얼마인지 구하는 문제다.

단 상어의 이동과 먹을 수 있는 경우에 조건이 몇가지 존재한다.

  1. 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
  2. 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다
  3. 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
  4. 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.
  5. 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 
  6. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다.

조건이 좀 많아보이지만, 하나 하나 살펴보면 구현에 크게 어렵지는 않다.

 

먼저 입력 크기를 보게 되면 N의 최대 크기는 20으로 맵의 최대 면적은 400보다 작거나 같다.

 

모든 지점을 탐색하며 먹을 수 있는 먹이를 찾을 때, 나이브하게 연산의 수를 구하면 160,000회를 넘지 않는다.

 

따라서 상어의 위치에 따라 먹을 수 있는 모든 먹이를 찾는 방식으로 구현하였다.

 

전체적인 흐름은 다음과 같다.

 

기저조건을 살펴보면, 먹을 수 있는 먹이가 존재하지 않을 경우 종료하게 된다.

 

따라서 먹을 수 있는 물고기가 존재하는지 여부를 먼저 살펴봐야한다.

 

먹을 수 있는 물고기의 존재 여부는 `List`로 확인하였다.

 

물고기 탐색을 진행하며 먹을 수 있는 물고기를 해당 리스트에 저장하게 되고 따라서 리스트의 크기가 0이라면 먹을 수 있는 물고기가 없다고 판단하였다.

/**
 * 상어가 물고기를 잡아먹을 수 있는지 검증하는 메소드
 * @return 잡아먹을 물고기가 존재하면 true, 아니라면 false를 반환
 */
private static boolean canEatFish() {
    // 먹을 수 있는 물고기를 저장할 리스트 생성
    eatableFish = new ArrayList<>();
    // 물고기 탐색
    findFish();
    // 먹을 수 있는 물고기를 조건에 맞게 정렬 (거리 -> 상단 -> 좌측)
    Collections.sort(eatableFish);
    // 먹을 수 있는 물고기가 없는 경우 
    if (eatableFish.size() == 0) {
        return false;
    }
    // 먹을 수 있는 물고기가 있는 경우 
    return true;
}

 

그렇다면, 먹을 수 있는 물고기는 어떻게 탐색할까 하다가 최소거리의 물고기가 우선순위이므로 BFS를 사용하였다.

 

상어의 위치를 초기위치로 설정한 뒤, BFS를 진행하게 되는데, 이 때 문제의 제약 조건들이 사용되게 된다.

 

탐색중인 위치에서 4방 탐색(`tempRow`, `tempCol`)을 진행하게 된다.

 

"상어의 크기보다 큰 물고기가 있을 경우 지나갈 수 없다"

// 상어의 크기보다 큰 물고기가 있을 경우 지나갈 수 없다
if (map[tempRow][tempCol] > shark.size) {
    continue;
}

 

"상어의 크기보다 작은 물고기는 잡아먹을 수 있다."

// 빈 공간이 아니고, 상어의 크기보다 작다면, 먹을 수 있는 물고기이므로 거리와 함께 저장
if (map[tempRow][tempCol] != 0 &&map[tempRow][tempCol] < shark.size) {
    eatableFish.add(new Fish(new Pos(tempRow, tempCol), map[tempRow][tempCol], currDist + 1));
}

 

이 외의 부분은 기본적인 BFS 코드와 동일하다.

 

리스트에 잡아먹을 수 있는 물고기를 저장했다면, 그 중 우선순위가 높은 물고기를 선택해야한다.

 

따라서 물고기 클래스에 `Comparable<>`인터페이스를 구현하여 우선순위를 설정하였다.

// 물고기 클래스
static class Fish implements Comparable<Fish> {
    Pos pos;
    int size;
    int distFromShark; // 상어로부터 떨어진 거리

    public Fish(Pos pos, int size, int distFromShark) {
        super();
        this.pos = pos;
        this.size = size;
        this.distFromShark = distFromShark;
    }

    // 정렬 우선순위
    // 1. 상어로부터 거리(오름차순)
    // 2. 전체 맵 기준 상단(오름차순)
    // 3. 전체 맵 기준 좌측(오름차순)
    @Override
    public int compareTo(Fish o) {
        if (this.distFromShark == o.distFromShark) {
            if (this.pos.x == o.pos.x) {
                return Integer.compare(this.pos.y, o.pos.y);
            }
            return Integer.compare(this.pos.x, o.pos.x);
        }
        return Integer.compare(this.distFromShark, o.distFromShark);
    } 	
}

 

위의 과정을 잡아먹을 물고기가 있을 때 까지 반복하면 된다.

 

잡아 먹을 물고기가 존재한다면, 상어 객체의 상태를 수정해주고, 맵의 잡아먹힌 물고기의 위치를 0으로 수정해주어야한다.

// 잡아먹을 물고기가 잇을 때까지 반복
while (canEatFish()) {
    // 가장 조건에 부합하는 물고기 한마리 선택
    Fish currEatFish = eatableFish.get(0);
    // 상어의 물고기 카운트 증가
    shark.fishCnt++;
    // 상어의 크기를 늘릴 수 있는 경우, 늘리기
    if (shark.fishCnt == shark.size) {
        shark.size++;
        shark.fishCnt = 0;
    }

    // 상어로부터 떨어진 거리만큼 총 소요 시간에 더하기
    totalTime += currEatFish.distFromShark;
    // 잡아 먹은 물고기가 있던 위치를 0으로 설정
    map[currEatFish.pos.x][currEatFish.pos.y] = 0;
    // 상어 위치를 잡아 먹은 위치로 변경
    shark.pos.x = currEatFish.pos.x;
    shark.pos.y = currEatFish.pos.y;
}

 

2. 코드

package boj;

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

/**
 * [BOJ] - 아기 상어 / 16236번 
 * @author JinHxxxxKim
 * 
 * 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
 * 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
 * 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다
 * 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
 * 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.
 * 
 * 1. 아기 상어의 현재 위치에서 BFS 탐색을 실행하며, 먹을 수 있는 물고기를 찾고 저장한다.
 * 2. 먹을 수 있는 물고기를 주어진 조건대로 정렬한다.
 * 3. 가장 앞에 있는 물고기를 먹는다.
 * 4. 먹은 물고기의 크기와 상어의 크기가 같다면, 상어의 물고기 카운트를 하나 증가시킨다.
 * 		4-1. 상어의 물고기 카운트가 상어의 크기와 같다면, 상어의 크기를 증가시키고 물고기 카운트를 0으로 초기화한다.
 * 5. 먹을 수 있는 물고기를 저장한 리스트의 크기가 0이라면 종료하고 소요 시간을 출력한다. 
 */
public class Sol_16236 {
	static final int[] dx = new int[] { -1, 0, 1, 0 };
	static final int[] dy = new int[] { 0, 1, 0, -1 };
	private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	private static StringTokenizer st;

	static int N;
	static int[][] map;
	static Shark shark;
	static List<Fish> eatableFish; // 먹을 수 있는 물고기 정보
	static boolean[][] isVisited; 
	static int[][] dist; // 상어로부터의 거리

	public static void main(String[] args) throws Exception {
		N = Integer.parseInt(br.readLine().trim());
		map = new int[N][N];

		for (int row = 0; row < N; ++row) {
			st = new StringTokenizer(br.readLine().trim());
			for (int col = 0; col < N; ++col) {
				map[row][col] = Integer.parseInt(st.nextToken());
				if (map[row][col] == 9) {
					// 상어의 위치만 저장하고, 탐색을 위해 해당 위치는 0으로 초기화
					shark = new Shark(new Pos(row, col), 2, 0);
					map[row][col] = 0;
				}
			}
		}

		int totalTime = 0;

		// 잡아먹을 물고기가 잇을 때까지 반복
		while (canEatFish()) {
			// 가장 조건에 부합하는 물고기 한마리 선택
			Fish currEatFish = eatableFish.get(0);
			// 상어의 물고기 카운트 증가
			shark.fishCnt++;
			// 상어의 크기를 늘릴 수 있는 경우, 늘리기
			if (shark.fishCnt == shark.size) {
				shark.size++;
				shark.fishCnt = 0;
			}

			// 상어로부터 떨어진 거리만큼 총 소요 시간에 더하기
			totalTime += currEatFish.distFromShark;
			// 잡아 먹은 물고기가 있던 위치를 0으로 설정
			map[currEatFish.pos.x][currEatFish.pos.y] = 0;
			// 상어 위치를 잡아 먹은 위치로 변경
			shark.pos.x = currEatFish.pos.x;
			shark.pos.y = currEatFish.pos.y;
		}

		System.out.println(totalTime);
	}

	/**
	 * 상어가 물고기를 잡아먹을 수 있는지 검증하는 메소드
	 * @return 잡아먹을 물고기가 존재하면 true, 아니라면 false를 반환
	 */
	private static boolean canEatFish() {
		// 먹을 수 있는 물고기를 저장할 리스트 생성
		eatableFish = new ArrayList<>();
		// 물고기 탐색
		findFish();
		// 먹을 수 있는 물고기를 조건에 맞게 정렬 (거리 -> 상단 -> 좌측)
		Collections.sort(eatableFish);
		// 먹을 수 있는 물고기가 없는 경우 
		if (eatableFish.size() == 0) {
			return false;
		}
		// 먹을 수 있는 물고기가 있는 경우 
		return true;
	}

	/**
	 * 잡아 먹을 물고기를 탐색하는 메소드(BFS)
	 */
	private static void findFish() {
		Queue<Pos> q = new ArrayDeque<>();
		// 매 탐색마다 초기화 해준다.
		isVisited = new boolean[N][N];
		dist = new int[N][N];
		
		// 초기 위치는 상어 위치
		q.offer(shark.pos);
		isVisited[shark.pos.x][shark.pos.y] = true;
		dist[shark.pos.x][shark.pos.y] = 0;
		while (!q.isEmpty()) {
			Pos currPos = q.poll();
			int currRow = currPos.x;
			int currCol = currPos.y;
			int currDist = dist[currRow][currCol];

			// 4방 탐색
			for (int dir = 0; dir < 4; ++dir) {
				int tempRow = currRow + dx[dir];
				int tempCol = currCol + dy[dir];
					
				// 범위 검증
				if (tempRow < 0 || tempCol < 0 || tempRow >= N || tempCol >= N) {
					continue;
				}
				// 방문 검증
				if (isVisited[tempRow][tempCol]) {
					continue;
				}
				// 상어의 크기보다 큰 물고기가 있을 경우 지나갈 수 없다
				if (map[tempRow][tempCol] > shark.size) {
					continue;
				}
				
				q.offer(new Pos(tempRow, tempCol));
				isVisited[tempRow][tempCol] = true;
				dist[tempRow][tempCol] = currDist + 1;
				// 빈 공간이 아니고, 상어의 크기보다 작다면, 먹을 수 있는 물고기이므로 거리와 함께 저장
				if (map[tempRow][tempCol] != 0 &&map[tempRow][tempCol] < shark.size) {
					eatableFish.add(new Fish(new Pos(tempRow, tempCol), map[tempRow][tempCol], currDist + 1));
				}
			}
		}
	}

	// 물고기 클래스
	static class Fish implements Comparable<Fish> {
		Pos pos;
		int size;
		int distFromShark; // 상어로부터 떨어진 거리

		public Fish(Pos pos, int size, int distFromShark) {
			super();
			this.pos = pos;
			this.size = size;
			this.distFromShark = distFromShark;
		}

		// 정렬 우선순위
		// 1. 상어로부터 거리(오름차순)
		// 2. 전체 맵 기준 상단(오름차순)
		// 3. 전체 맵 기준 좌측(오름차순)
		@Override
		public int compareTo(Fish o) {
			if (this.distFromShark == o.distFromShark) {
				if (this.pos.x == o.pos.x) {
					return Integer.compare(this.pos.y, o.pos.y);
				}
				return Integer.compare(this.pos.x, o.pos.x);
			}
			return Integer.compare(this.distFromShark, o.distFromShark);
		} 	
	}

	// 상어 클래스
	static class Shark {
		Pos pos;
		int size;
		int fishCnt;
		
		public Shark(Pos pos, int size, int fishCnt) {
			super();
			this.pos = pos;
			this.size = size;
			this.fishCnt = fishCnt;
		}	
	}

	// 위치 클래스
	static class Pos {
		int x, y;

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

 

3. 디버깅

전체적으로 문제를 코드를 꼼꼼하게 못 짜서 자잘한 실수들로 인해 디버깅을 진행했었다.

 

초기 상어의 위치를 0으로 설정하지 않아 참색이 틀어지는 경우, 빈 공간을 물고기로 인식하여 저장하는 경우, 물고기와의 거리를 더해야하는데 좌표 차이를 더하는 등, 델타 배열 초기화 실수 등...의 자잘한 실수들이 많이 나왔던 문제였다.

 

코드를 짤 때 좀 더 천천히 짜나가야겠다.

4. 결과

'알고리즘' 카테고리의 다른 글

[BOJ] - 1로 만들기 / 1463번 (Java)  (0) 2024.02.28
[BOJ] - 최단경로 / 1753번 (Java)  (0) 2024.02.28
[BOJ] - 외판원 순회 2 / 10971번 (Java)  (1) 2024.02.26
[BOJ] - 연구소 / 14502번 (Java)  (1) 2024.02.26
[BOJ] - 거짓말 / 1043번 (Java)  (1) 2024.02.25
알고리즘 관련 글
더 보기

티스토리툴바