[백준/16236/Java] 아기상어

 

문제:

16236번: 아기 상어 (acmicpc.net)

16236번: 아기 상어

 

 

문제를 먼저 풀고 오시는 것을 추천합니다.
이 문제의 풀이는 BFS 외에도 다양한 방법이 있을 수 있으며 제가 보여드리는 풀이는 그 중 하나입니다.

 

 

문제분석

문제에 아기상어에 대한 제한조건이 많은 편입니다.

 

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

 

아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수입니다. 아기 상어의 처음 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동합니다.

 

아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있습니다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있습니다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있습니다. 그리고 물고기를 먹는데 걸리는 시간은 없고, 물고기를 먹으면, 그 칸은 빈 칸이 됩니다.

아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가합니다. 

 

아기상어가 어디로 이동할지 결정하는 방법을 정리하면 다음과 같습니다.

1. 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청합니다. 즉, 더이상 이동하지 않고 종료됩니다.

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

 

입력

첫째 줄에 공간의 크기 N(2 ≤ N ≤ 20)이 주어집니다.

둘째 줄부터 N개의 줄에 공간의 상태가 주어집니다. 공간의 상태는 0, 1, 2, 3, 4, 5, 6, 9로 이루어져 있고, 아래와 같은 의미를 가집니다.

• 0: 빈 칸
• 1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
• 9: 아기 상어의 위치

아기 상어는 공간에 한 마리만 존재합니다.

 

출력

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

즉, 더이상 먹을 수 있는 물고기가 없으면 그 때까지의 시간을 출력하면 됩니다.

 

 

풀이

아기상어는 물고기를 찾아야 하는데 먼저 아기상어 크기보다 같거나 작은 물고기 목록을 찾습니다.

크기가 같은 물고기는 통과만 가능하므로 이동만 해야 하고 크기가 작은 물고기만 먹을 수 있습니다.

 

크기가 작은 물고기가 여러 마리일 경우 가장 위에 있고 가장 왼쪽에 있는 물고기를 먹어야 합니다.

그리고 자신의 크기와 같은 수의 물고기를 먹어야 크기가 1 증가합니다. 

 

더 이상 크기가 작은 물고기를 먹을 수 없을 때까지 위의 행동을 반복합니다.

 

예제풀이

아기상어에 있는 예제로 어떻게 동작하는지 확인해보겠습니다.

 

예제1

아기상어의 처음 크기는 2이고 작은 물고기가 1마리 존재합니다.

// 입력
0 0 1
0 0 0
0 9 0

따라서, BFS를 사용하며, 방문 배열을 0으로 초기화합니다.

아기상어가 있는 곳부터 시작하며, 1부터 시작합니다.

그리고 BFS로 이동하면서 시간을 1씩 더해주면 이렇게 됩니다.

물고기 위치의 거리는 4이지만 처음에 1부터 시작했으므로 이동한 거리는 3이 됩니다.

// 풀이
3

// 방문배열
[4, 3, 4]
[3, 2, 3]
[2, 1, 2]

 

예제2

이번에는 물고기 크기가 1, 2, 3, 4로 순서대로 있는 경우입니다.

 

상어크키가 2이므로 2보다 같거나 작은 물고기까지의 거리를 BFS로 계산합니다.

크기가 1인 물고기가 2마리 존재하므로 가장 위에 있는 (0, 3) 위치에 있는 크기 1인 물고기를 먹습니다.

 

이제 (0, 3)부터 BFS로 시작하여 크기가 2보다 작은 물고기를 찾으러 갑니다.

(3, 0) 위치에 있는 크기 1 물고기를 먹으면 2마리를 먹었으므로 크기가 3이 됩니다.

 

 

크기가 3이 되었으므로 이제 크기가 2인 물고기를 먹을 수 있습니다.

바로 옆에 있는 (3, 1) 위치의 물고기를 먹습니다.

 

그 다음 크기가 2인 (0, 2)인 물고기를 먹을 수 있습니다.

 

크기가 2인 물고기를 더 찾아보아도 존재하지 않기 때문에 더이상 먹을 수 있는 물고기가 없습니다.

따라서, 엄마 상어에게 도움을 요청하고 14를 출력하면 됩니다.

 

 

소스

상어를 클래스로 정의하고 위치정보인 i, j와 이동거리인 move변수를 선언합니다.

그리고 가장 위, 가장 왼쪽 물고기를 찾기 위하여 정렬을 이용할 생각이므로 정렬 인터페이스를 구현합니다.

class Shark implements Comparable<Shark> {
	int i;
	int j;
	int move;

	public Shark(int i, int j, int move) {
		this.i = i;
		this.j = j;
		this.move = move;
	}

	@Override
	public int compareTo(Shark t) {
		// 거리순
		if (this.move < t.move)
			return -1;
		else if (this.move > t.move)
			return 1;

		// 가장 위, 가장 왼쪽
		if (this.i < t.i)
			return -1;
		else if (this.i > t.i)
			return 1;

		if (this.j < t.j)
			return -1;
		else if (this.j > t.j)
			return 1;

		return 0;
	}
}

 

지도배열은 m, 방문배열은 v로 선언하였습니다.

findFish 함수에서 이동 가능 및 먹을 수 있는 물고기 목록을 찾아서 리턴하고

eat 함수에서 가장 위, 가장 왼쪽 물고기를 먼저 먹기 위하여 정렬을 하고 먹습니다.

물고기를 먹으면 지도배열에서 해당 위치를 0으로 변경합니다.

먹은 개수를 count 변수에 1을 더하여 저장합니다.

크기와 동일한 수만큼 먹으면 상어크기가 커집니다.

 

전체 소스는 이렇게 됩니다.

print 함수를 따로 구현했는데 물고기를 먹은 위치, 상어 크기, 먹은 물고기 수, 이번에 이동한 거리, 전체 이동한 거리를 출력하였으므로 검증하실 때 사용하시면 됩니다.

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

public class Main {
	static int N;

	static int m[][];
	static int v[][];

	static int ANSWER = 0;
	static int size = 2;
	static int count = 0;

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

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

		m = new int[N][N];
		v = new int[N][N];

		int n = 0;
		Shark shark = new Shark(0, 0, 0);
		StringTokenizer st = null;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				m[i][j] = Integer.valueOf(st.nextToken());
				if (m[i][j] == 9) {
					shark = new Shark(i, j, 0);
					m[i][j] = 0;
				}
			}
		}

		List<Shark> sharkList = null;
		do {
			sharkList = findFish(shark);
			if (sharkList == null || sharkList.size() == 0)
				break;

//				System.out.println(sharkList);
			shark = eat(sharkList);
//				print(shark);
			init(shark);
		} while (sharkList != null);

		System.out.println(ANSWER);
	}

	private static void init(Shark shark) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				v[i][j] = 0;
			}
		}
		shark.move = 0;
	}

	private static void print(Shark shark) {
		for (int i = 0; i < N; i++) {
			System.out.println(Arrays.toString(v[i]));
		}
		System.out.println("i = " + shark.i + ", j = " + shark.j + ", size = " + size + ", count = " + count
				+ ", move = " + shark.move + ", ans = " + ANSWER);
		System.out.println();
	}

	private static List<Shark> findFish(Shark shark) {
		List<Shark> sharkList = new ArrayList<Shark>();

		Queue<Shark> q = new LinkedList<Shark>();

		q.add(shark);
		v[shark.i][shark.j] = 1;

		int i, j;
		while (q.isEmpty() == false) {
			shark = q.remove();
			i = shark.i;
			j = shark.j;

			if (m[i][j] != 0 && m[i][j] < size) {
				sharkList.add(shark);
			}

			if (j - 1 >= 0 && v[i][j - 1] == 0 && m[i][j - 1] <= size) {
				// 좌
				v[i][j - 1] = v[i][j] + 1;
				q.add(new Shark(i, j - 1, shark.move + 1));
			}
			if (i - 1 >= 0 && v[i - 1][j] == 0 && m[i - 1][j] <= size) {
				// 상
				v[i - 1][j] = v[i][j] + 1;
				q.add(new Shark(i - 1, j, shark.move + 1));
			}
			if (i + 1 < N && v[i + 1][j] == 0 && m[i + 1][j] <= size) {
				// 하
				v[i + 1][j] = v[i][j] + 1;
				q.add(new Shark(i + 1, j, shark.move + 1));
			}
			if (j + 1 < N && v[i][j + 1] == 0 && m[i][j + 1] <= size) {
				// 우
				v[i][j + 1] = v[i][j] + 1;
				q.add(new Shark(i, j + 1, shark.move + 1));
			}
		}

		return sharkList;
	}

	private static Shark eat(List<Shark> sharkList) {
		Collections.sort(sharkList);

		Shark shark = sharkList.get(0);

		m[shark.i][shark.j] = 0;
		ANSWER += shark.move;
		count++;
		if (size == count) {
			size++;
			count = 0;
		}

		return shark;
	}
}

class Shark implements Comparable<Shark> {
	int i;
	int j;
	int move;

	public Shark(int i, int j, int move) {
		this.i = i;
		this.j = j;
		this.move = move;
	}

	@Override
	public int compareTo(Shark t) {
		// 거리순
		if (this.move < t.move)
			return -1;
		else if (this.move > t.move)
			return 1;

		// 가장 위, 가장 왼쪽
		if (this.i < t.i)
			return -1;
		else if (this.i > t.i)
			return 1;

		if (this.j < t.j)
			return -1;
		else if (this.j > t.j)
			return 1;

		return 0;
	}

	@Override
	public String toString() {
		return "(" + i + "," + j + "=" + move + ")";
	}
}