[백준 - Java] 16236번 : 아기 상어

문제

www.acmicpc.net/problem/16236

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 0
0 0 0
0 9 0

예제 출력 1

0

 

예제 입력 2

3
0 0 1
0 0 0
0 9 0

예제 출력 2 

3

 

예제 입력 3

4
4 3 2 1
0 0 0 0
0 0 9 0
1 2 3 4

예제 출력 3

14

 

예제 입력 4 

6
5 4 3 2 3 4
4 3 2 3 4 5
3 2 9 5 6 6
2 1 2 3 4 5
3 2 1 6 5 4
6 6 6 6 6 6

예제 출력 4 

60

 

예제 입력 5 

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

예제 출력 5 

48

 

예제 입력 6 

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

예제 출력 6

39

구현

상어의 현재 위치에서 가장 최단 거리에 있는 작은 물고기들을 BFS로 탐색해나가면 된다.

탐색을 통해 작은 물고기 찾으면 그 위치로 이동하고 먹은 횟수, 탐색 시간을 조건에 맞게 변경하는 것을 반복한다.

더 이상 진행할 수 없을 때까지 탐색하고 그때의 시간을 출력하면 된다.

조건

먼저 상어와 물고기의 정보를 담기 위한 이차원 배열 map을 생성한다.

map의 조건은 아래와 같다.

 

• N * N 크기 (2 ≤ N ≤ 20)

• 0 : 빈칸

• 1, 2, 3, 4, 5, 6 : 칸에 있는 물고기의 크기

• 9 : 아기 상어의 위치

public static int[][] map;
public static int[][] check; // 상어의 이동 거리를 체크하기 위한 배열 
public static int N; 
public static int SX, SY; // 상어의 x, y 좌표 
public static int size = 2; // 상어의 초기 크기 
public static int eat = 0; // 상어가 몇 마리의 물고기를 먹었는지 판별하기 위한 변수 
public static int minD, minX, minY; //최소 거리, 최소 x값, 최소 y값 
public static int ans = 0; // 정답 변수 
public static int[][] dir = {{-1, 0}, {0, -1}, {1, 0},  {0, 1}}; // 상, 좌, 하, 우 이동을 위한 배열

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];
	check = 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 n = Integer.parseInt(st.nextToken());
			if(n == 9) { // 상어 위치 저장 
				SX = i;
				SY = j;
			}
			map[i][j] = n;
		}
	}

	//아기 상어 이동

	// 더이상 먹을 물고기가 없다면 정답 출력 
	System.out.println(ans);
}

 

상어가 이동하며 물고기를 먹는 조건이 많다.

이를 처리하기 위한 변수는 아래와 같다.

 

• check 배열 : BFS를 수행하며 상어가 이동한 거리를 체크하기 위한 배열이다.

• SX, SY : 상어의 x, y 좌표 값을 담을 변수

• size : 상어의 크기 (초기값 2)

• eat : 상어 크기 증가를 위해 몇 마리의 물고기를 먹었는지를 담는 변수

• minD : 최소 거리 (이동 거리가 가장 짧은 물고기를 판별하기 위함)

• minX : 최소 x값 (x 거리가 가장 짧은 물고기를 판별하기 위함)

• minY : 최소 y값 (y 거리가 가장 짧은 물고기를 판별하기 위함)

본격적으로 상어 이동을 구현하기 위한 조건을 알아보자.

상어 이동 조건 

• 처음 상어의 크기는 2 (int size = 2)

• 1초에 상하좌우로 인접한 한 칸씩 이동

• 상어 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있음

• 한 번 이동에 1초 (상어의 총 이동 거리 = 정답 시간)

• 더 이상 먹을 수 있는 물고기가 공간에 없다면 이동 종료

더 이상 먹을 물고기가 없을 때까지 while문을 반복하며, BFS를 통해 상어가 이동하고 물고기를 찾아 잡아먹는다.

 

BFS를 수행하는 과정에서 상어를 이동시키고 현재 상어 위치에서 인접한 물고기가 있는 곳을 탐색한다.

 

// 아기 상어 이동 시작 
while(true) {
	initCheck(); // BFS 재탐색을 위한 초기화 함수 

	bfs(SX, SY); // BFS로 상어를 이동시키며, 최단 거리로 만날 수 있는 물고기를 탐색 

	if(minX != Integer.MAX_VALUE && minY != Integer.MAX_VALUE) { // 물고기를 찾았다면 

	} else { //찾지 못했다면 종료 
		break;
	}
}

 

BFS를 수행할 때마다 initCheck() 함수를 통해 BFS를 위한 값들을 초기화시켜준다.

(위에서 설명했듯이 현재 상어의 위치에서 BFS를 통해 더 이상 먹을 물고기가 없을 때까지 상어가 이동하고 먹는 것이 반복되기 때문)

 

최소 거리, 최소 x값, 최소 y값을 모두 최댓값으로 초기화.

 

이동 거리를 판단하기 위한 check 배열도 -1로 초기화. (check 배열은 BFS를 수행하며 한 칸씩 이동할 때마다 +1 된다.)

 

public static void initCheck() {
	minX = Integer.MAX_VALUE;
	minY = Integer.MAX_VALUE;
	minD = Integer.MAX_VALUE;

	for(int i = 0; i < N; i++) {
		for(int j = 0; j < N; j++) {
			check[i][j] = -1;
		}
	}
}

 

물고기를 찾은 경우를 구현하기 전, 먼저 BFS 부분을 다음으로 구현해보자.

물고기 먹는 조건

• 상어 크기보다 작은 물고기만 먹을 수 있음 (크기가 같다면 먹을 순 없지만, 지나갈 순 있음)

• 먹을 수 있는 물고기가 1 마리면 그 물고기를 먹음

• 1마리 이상이면 상어 위치에서 물고기를 먹기 위해 이동하는 거리가 가장 짧은 물고기를 먹음

• 거리가 짧은 물고기가 1마리 이상이면 가장 위에 있는 물고기

• 가장 위에 잇는 물고기가 1마리 이상이면 가장 왼쪽에 있는 물고기를 먹는다.

• 물고기를 먹으면 그 칸은 빈칸이 됨

• 자신의 크기와 같은 수의 물고기를 먹으면 크기가 1 증가

 

1. BFS를 위해 큐를 생성하고 현재 상어의 위치를 넣어준다.

map에 상어의 위치를 빈칸으로 만들어주고, check에는 상어의 이동을 시작하기 위해 0으로 만들어준다.

 

2. 본격적으로 큐가 빌 때까지 BFS를 수행하며 인접한 물고기가 있는 곳을 탐색한다.

총 4방향을 탐색하는데, dir 배열을 이용해 쉽게 상어의 위치를 상하좌우 이동시키며 새로운 위치를 구한다.

 

3. 새로운 위치가 map 범위를 벗어나지 않고, 이미 갔던 곳이 아니며, 현재 상어 크기와 같거나 작은 물고기가 있는 칸이라면

이동했다는 의미로 check 배열의 이동거리를 1 증가시킨다.

 

4. 그런데 만약 새로운 칸이 현재 상어 크기보다 작은 물고기가 있는 칸이라면 물고기를 먹을 수 있기에 세세한 조건을 다시 판별한다.

여기서 먹을 수 있는 물고기가 1마리 이상인 경우가 있을 수 있기 때문에 minD, minX, minY 변수를 사용해 판별하는 것이다.

(처음 먹을 수 있는 물고기를 발견한 경우 minD, minX, minY 값이 모두 Integer.MAX_VALUE 정수 최댓값으로 설정되어 있다.)

발견한 물고기까지의 이동거리, 물고기의 x, y 값을 비교해 조건에 충족한다면 minD, minX, minY값을 발견한 물고기의 값으로 변경해준다.

 

5. 그리고 다시 새로운 상어의 위치를 큐에 넣어주고 위의 과정이 반복된다.

 

public static void bfs(int x, int y) {
	// 1
	Queue<Shark> que = new LinkedList<Shark>();
	que.add(new Shark(x, y)); // 상어 이동 시작 
	map[x][y] = 0; 
	check[x][y] = 0; 

	// 2
	while(!que.isEmpty()) {
		Shark cur = que.poll();
		x = cur.sx;
		y = cur.sy;

		// 4방향 탐색 
		for(int i = 0; i < 4; i++) {
			int nx = x + dir[i][0];
			int ny = y + dir[i][1];
            
			// 3. map 범위를 벗어나면 이동 X 
			if(nx < 0 || nx >= N || ny < 0 || ny >= N) 
				continue;

			// 이미 갔던 곳이고, 현재 상어의 크기보다 크면 이동 X
			if(check[nx][ny] != -1 || map[nx][ny] > size) 
				continue;

			// 위의 조건을 모두 벗어난 이동할 수 있는 곳이라면 
			check[nx][ny] = check[x][y] + 1; //이동 거리 1 증가 

			// 4. 그런데 이곳이 현재의 아기 상어보다 작은 물고기가 있는 곳이라면 
			if(map[nx][ny] != 0 && map[nx][ny] < size) { 
				if(check[nx][ny] < minD) {
					minX = nx;
					minY = ny;
					minD = check[nx][ny];
				} else if(check[nx][ny] == minD) { //거리가 가까운 물고기가 많다면 
					if(nx < minX) { //가장 위쪽에 있는 물고기 먹음
						minX = nx;
						minY = ny;
					} else if(nx == minX) { //가장 위쪽에 있는 물고기가 많다면 
						if(ny < minY) { //가장 위쪽 중, 가장 왼쪽 물고기 먹음 
							minX = nx;
							minY = ny;
						}
					}
				}
			}
            // 5
			que.add(new Shark(nx, ny));
		}
	}	
}

 

물고기를 먹든 안 먹든 BFS 함수 후

먹을 수 있는 물고기를 BFS를 통해 이동하며 찾았다면 MAX값으로 초기화되어 있던 minX값이 변경되었을 것이다. (minY, minD 마찬가지)

이때의 최소 이동 거리가 바로 구하는 시간이기에 정답 변수에 추가해준다.

그리고 eat값을 1 증가시켜 먹었다는 것을 나타내 준다.

증가 후 상어의 현재 크기와 먹은 물고기수가 같다면 상어의 크기를 1 증가시켜준다.

마지막으로 상어의 위치를 이동시키면 한 번의 먹이 찾기 과정이 끝난다.

 

만약 minX값이 MAX값 그대로라면 물고기를 찾지 못한 것임으로 while문을 종료하고 정답을 출력한 뒤 끝낸다.

 

// 아기 상어 이동 시작 
while(true) {
	initCheck(); 
	bfs(SX, SY);

	if(minX != Integer.MAX_VALUE) { //물고기를 찾았다면 
		ans += minD; //그때의 이동 거리가 이동 시간이니 정답 변수에 추가 
		
		eat++; //물고기 먹었으니 +1
		if(size == eat) { //아기 상어가 자신의 크기와 같은 수의 물고기를 먹었다면, 크기 1 증가 
			size++;
			eat = 0;
		}

		//아기 상어 위치 이동 
		map[minX][minY] = 0;
		SX = minX;
		SY = minY;
	} else { //찾지 못했다면 종료 
		break;
	}
}

//더이상 먹을 물고기가 없다면 정답 출력 
System.out.println(ans);
}

전체 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	public static int[][] map;
	public static int[][] check; // 상어의 이동 거리를 체크하기 위한 배열 
	public static int N; 
	public static int SX, SY; // 상어의 x, y 좌표 
	public static int size = 2; // 상어의 초기 크기 
	public static int eat = 0; // 상어가 몇 마리의 물고기를 먹었는지 판별하기 위한 변수 
	public static int minD, minX, minY; //최소 거리, 최소 x값, 최소 y값 
	public static int ans = 0; // 정답 변수 
	public static int[][] dir = {{-1, 0}, {0, -1}, {1, 0},  {0, 1}}; // 상, 좌, 하, 우

	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];
		check = 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 n = Integer.parseInt(st.nextToken());
				if(n == 9) { // 상어 위치 저장 
					SX = i;
					SY = j;
				}
				map[i][j] = n;
			}
		}

		// 아기 상어 이동 시작 
		while(true) {
			initCheck(); // BFS 재탐색을 위한 초기화 함수 
			
			bfs(SX, SY); // BFS로 상어를 이동시키며, 최단 거리로 만날 수 있는 물고기를 탐색 

			if(minX != Integer.MAX_VALUE) { //물고기를 찾았다면 
				ans += minD; //그때의 이동 거리가 이동 시간이니 정답 변수에 추가 
				
				eat++; //물고기 먹었으니 +1
				if(size == eat) { //상어 크기와 같은 수의 물고기를 먹었다면, 크기 1 증가 
					size++;
					eat = 0;
				}
				
				//아기 상어 위치 이동 
				map[minX][minY] = 0;
				SX = minX;
				SY = minY;
			} else {
				break;
			}
		}
		
		//더이상 먹을 물고기가 없다면 정답 출력 
		System.out.println(ans);
	}

	public static void initCheck() {
		minX = Integer.MAX_VALUE;
		minY = Integer.MAX_VALUE;
		minD = Integer.MAX_VALUE;

		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				check[i][j] = -1;
			}
		}
	}

	public static void bfs(int x, int y) {
		Queue<Shark> que = new LinkedList<Shark>();
		que.add(new Shark(x, y)); // 상어 이동 시작 
		map[x][y] = 0; 
		check[x][y] = 0; 

		while(!que.isEmpty()) {
			Shark cur = que.poll();
			x = cur.sx;
			y = cur.sy;
			
			//4방향 탐색 
			for(int i = 0; i < 4; i++) {
				int nx = x + dir[i][0];
				int ny = y + dir[i][1];
                
				//map 범위를 벗어나면 이동 X 
				if(nx < 0 || nx >= N || ny < 0 || ny >= N) 
					continue;

				//이미 갔던 곳이고, 현재 상어의 크기보다 크면 이동 X
				if(check[nx][ny] != -1 || map[nx][ny] > size) 
					continue;
				
				//위의 조건을 모두 벗어난 이동할 수 있는 곳이라면 
				check[nx][ny] = check[x][y] + 1; //이동 거리 1 증가 

				//그런데 이곳이 현재의 아기 상어보다 작은 물고기가 있는 곳이라면 
				if(map[nx][ny] != 0 && map[nx][ny] < size) { 
					if(check[nx][ny] < minD) {
						minX = nx;
						minY = ny;
						minD = check[nx][ny];
					} else if(check[nx][ny] == minD) { //거리가 가까운 물고기가 많다면 
						if(nx < minX) { //가장 위쪽에 있는 물고기 먹음
							minX = nx;
							minY = ny;
						} else if(nx == minX) { //가장 위쪽에 있는 물고기가 많다면 
							if(ny < minY) { //가장 위쪽 중, 가장 왼쪽 물고기 먹음 
								minX = nx;
								minY = ny;
							}
						}
					}
				}
				que.add(new Shark(nx, ny));
			}
		}	
	}

}

class Shark {
	int sx;
	int sy;

	Shark(int sx, int sy) {
		this.sx = sx;
		this.sy = sy;
	}
}

다른 코드

위의 코드랑 비슷한 방법이긴 한데 eat, size, dist 변수들을 아예 상어 클래스에 주고 하는 방법이다.

그리고 상어의 이동과 물고기를 잡아먹는 부분은 따로 빼지 않고 한 번에 작성했다.

 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main2 {
	static int N; // 공간의 크기 N*N 
	static int SX, SY; // 상어의 x, y 좌표 
	static int[][] map;
	static boolean[][] visited;
	static int[][] dir = {{-1, 0}, {0, -1}, {1, 0},  {0, 1}}; // 상, 좌, 하, 우 

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		map = new int[N][N];
		visited = new boolean[N][N]; //먹이 탐색 시 중복 제거를 위한 배열 
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				map[i][j] = sc.nextInt();
				if(map[i][j] == 9) { // 아기 상어 최초 위치
					SX = i;
					SY = j;
				}
			}
		}

		solve();
	}

	static void solve() {
		Queue<Shark> queue = new LinkedList<>();

		queue.add(new Shark(SX, SY, 2, 0, 0)); //처음 아기 상어의 x좌표, y좌표, 크기, 먹은 횟수, 이동한 거리)
		visited[SX][SY] = true;

		// 걸린 시간
		int time = 0;

		while(!queue.isEmpty()) {
			//먹을 수 있는 물고기를 찾은 경우, 그 때의 값을 저장할 변수들 
			int minX = Integer.MAX_VALUE, minY = Integer.MAX_VALUE;
			int size = 0, eat = 0, dist = 0; 

			int qSize = queue.size();
			for(int j = 0; j < qSize; j++) {
				Shark shark = queue.poll();

				for(int i = 0; i < 4; i++) { //4방향 이동 
					int nx = shark.x + dir[i][0];
					int ny = shark.y + dir[i][1];

					if(nx < 0 || ny < 0 || nx >= N || ny >= N) continue; //map 범위를 벗어나면 이동 X 
					if(visited[nx][ny]) continue; //이미 갔던 곳이라면 이동 X 
					if(map[nx][ny] > shark.size) continue; //현재 상어의 크기보다 크면 이동 X 

					//위의 조건을 모두 벗어난 이동할 수 있는 곳이라면 
					visited[nx][ny] = true; //이동했으니 true 
					//이동한 상어의 위치와 크기, 먹은 횟수 그리고 한 칸 이동했다는 의미로 dist+1 값을 큐에 넣음 
					queue.add(new Shark(nx, ny, shark.size, shark.eat, shark.dist+1)); 

					//그런데 이곳이 현재의 아기 상어보다 작은 물고기가 있는 곳이라면 
					if(map[nx][ny] != 0 && map[nx][ny] != shark.size) {
						if(nx < minX) { //가장 가까이, 가장 위에 있는 물고기라면
							//그 때의 위치, 크기, 횟수, 거리+1 값을 변수에 저장 
							minX = nx;
							minY = ny;
							size = shark.size;
							eat = shark.eat;
							dist = shark.dist + 1;
						}else if(nx == minX) { //이미 가장 위에 있는 물고기라면
							if(ny < minY) { //가장 왼쪽에 있는 물고기인지 확인 후, 그 때의 값 변수에 저장  
								minX = nx;
								minY = ny;
								size = shark.size;
								eat = shark.eat;
								dist = shark.dist + 1;
							}
						}
					}
				}
			}
			
			//minX가 MAX값이 아니라 바뀌었다면 먹을 물고기가 있다는 것 
			if(minX != Integer.MAX_VALUE) {
				eat++; //물고기를 먹고, 먹은 횟수 추가 
			
				//아기 상어가 자신의 크기와 같은 수의 물고기를 먹었다면 
				if(eat == size) {
					size++; //크기 1 증가 
					eat = 0;
				}
				
				//아기 상어 위치 이동 
				map[SX][SY] = 0; //기존의 상어 위치는 이동되었으니 0으로 바꿔줌 
				map[minX][minY] = 9; 
				SX = minX; SY = minY;
				
				time += dist; //이동 거리가 시간과 같다.
				init(); //재탐색을 위한 방문 초기화
				queue.clear(); //이전에 탐색하던 것들은 필요 없으므로 제거
				
				//이동된 위치에서 다시 아기 상어 탐색 
				visited[minX][minY] = true;
				queue.add(new Shark(minX, minY, size, eat, 0));
			}
		}
		System.out.println(time); //더이상 먹을 물고기가 없을 때, 지금까지 누적된 시간 출력 후 종료 
	}
	
	// 최적의 먹이를 먹고, 다시 먹이 탐색하기 위해 초기화 
	static void init() {
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++)
				visited[i][j] = false;
		}
	}

	static class Shark{
		int x, y, size, eat, dist;

		Shark(int x, int y, int size, int eat, int dist){
			this.x = x;
			this.y = y;
			this.size = size;
			this.eat = eat;
			this.dist = dist;
		}
	}
}

GITHUB

github.com/KwonMinha/BOJ/tree/master/BOJ%2316236/src

KwonMinha/BOJ