[Baekjoon] 어른 상어

👀 문제 설명

문제

청소년 상어는 더욱 자라 어른 상어가 되었다. 상어가 사는 공간에 더 이상 물고기는 오지 않고 다른 상어들만이 남아있다. 상어에는 1 이상 M 이하의 자연수 번호가 붙어 있고, 모든 번호는 서로 다르다. 상어들은 영역을 사수하기 위해 다른 상어들을 쫓아내려고 하는데, 1의 번호를 가진 어른 상어는 가장 강력해서 나머지 모두를 쫓아낼 수 있다.

N×N 크기의 격자 중 M개의 칸에 상어가 한 마리씩 들어 있다. 맨 처음에는 모든 상어가 자신의 위치에 자신의 냄새를 뿌린다. 그 후 1초마다 모든 상어가 동시에 상하좌우로 인접한 칸 중 하나로 이동하고, 자신의 냄새를 그 칸에 뿌린다. 냄새는 상어가 k번 이동하고 나면 사라진다.

각 상어가 이동 방향을 결정할 때는, 먼저 인접한 칸 중 아무 냄새가 없는 칸의 방향으로 잡는다. 그런 칸이 없으면 자신의 냄새가 있는 칸의 방향으로 잡는다. 이때 가능한 칸이 여러 개일 수 있는데, 그 경우에는 특정한 우선순위를 따른다. 우선순위는 상어마다 다를 수 있고, 같은 상어라도 현재 상어가 보고 있는 방향에 따라 또 다를 수 있다. 상어가 맨 처음에 보고 있는 방향은 입력으로 주어지고, 그 후에는 방금 이동한 방향이 보고 있는 방향이 된다.

모든 상어가 이동한 후 한 칸에 여러 마리의 상어가 남아 있으면, 가장 작은 번호를 가진 상어를 제외하고 모두 격자 밖으로 쫓겨난다.

<그림 1>

<그림 1>은 맨 처음에 모든 상어가 자신의 냄새를 뿌린 상태를 나타내며, <표 1>에는 각 상어 및 현재 방향에 따른 우선순위가 표시되어 있다. 이 예제에서는 k = 4이다. 왼쪽 하단에 적힌 정수는 냄새를 의미하고, 그 값은 사라지기까지 남은 시간이다. 좌측 상단에 적힌 정수는 상어의 번호 또는 냄새를 뿌린 상어의 번호를 의미한다.

<그림 2>

<그림 3>

<그림 2>는 모든 상어가 한 칸 이동하고 자신의 냄새를 뿌린 상태이고, <그림 3>은 <그림 2>의 상태에서 한 칸 더 이동한 것이다. (2, 4)에는 상어 2과 4가 같이 도달했기 때문에, 상어 4는 격자 밖으로 쫓겨났다.

<그림 4>

<그림 5>

<그림 4>은 격자에 남아있는 모든 상어가 한 칸 이동하고 자신의 냄새를 뿌린 상태, <그림 5>는 <그림 4>에서 한 칸 더 이동한 상태를 나타낸다. 상어 2는 인접한 칸 중에 아무 냄새도 없는 칸이 없으므로 자신의 냄새가 들어있는 (2, 4)으로 이동했다. 상어가 이동한 후에, 맨 처음에 각 상어가 뿌린 냄새는 사라졌다.

이 과정을 반복할 때, 1번 상어만 격자에 남게 되기까지 몇 초가 걸리는지를 구하는 프로그램을 작성하시오.

 

입력

첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000)

그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미한다.

그 다음 줄에는 각 상어의 방향이 차례대로 주어진다. 1, 2, 3, 4는 각각 위, 아래, 왼쪽, 오른쪽을 의미한다.

그 다음 줄부터 각 상어의 방향 우선순위가 상어 당 4줄씩 차례대로 주어진다. 각 줄은 4개의 수로 이루어져 있다. 하나의 상어를 나타내는 네 줄 중 첫 번째 줄은 해당 상어가 위를 향할 때의 방향 우선순위, 두 번째 줄은 아래를 향할 때의 우선순위, 세 번째 줄은 왼쪽을 향할 때의 우선순위, 네 번째 줄은 오른쪽을 향할 때의 우선순위이다. 각 우선순위에는 1부터 4까지의 자연수가 한 번씩 나타난다. 가장 먼저 나오는 방향이 최우선이다. 예를 들어, 우선순위가 1 3 2 4라면, 방향의 순서는 위, 왼쪽, 아래, 오른쪽이다.

맨 처음에는 각 상어마다 인접한 빈 칸이 존재한다. 따라서 처음부터 이동을 못 하는 경우는 없다.

 

출력

1번 상어만 격자에 남게 되기까지 걸리는 시간을 출력한다. 단, 1,000초가 넘어도 다른 상어가 격자에 남아 있으면 -1을 출력한다.

 

예제 입력 1

5 4 4
0 0 0 0 3
0 2 0 0 0
1 0 0 0 4
0 0 0 0 0
0 0 0 0 0
4 4 3 1
2 3 1 4
4 1 2 3
3 4 2 1
4 3 1 2
2 4 3 1
2 1 3 4
3 4 1 2
4 1 2 3
4 3 2 1
1 4 3 2
1 3 2 4
3 2 1 4
3 4 1 2
3 2 4 1
1 4 2 3
1 4 2 3

 

예제 출력 1

14

 

예제 입력 2

4 2 6
1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 2
4 3
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3

 

예제 출력 2

26

 

예제 입력 3

5 4 1
0 0 0 0 3
0 2 0 0 0
1 0 0 0 4
0 0 0 0 0
0 0 0 0 0
4 4 3 1
2 3 1 4
4 1 2 3
3 4 2 1
4 3 1 2
2 4 3 1
2 1 3 4
3 4 1 2
4 1 2 3
4 3 2 1
1 4 3 2
1 3 2 4
3 2 1 4
3 4 1 2
3 2 4 1
1 4 2 3
1 4 2 3

 

예제 출력 3

-1

 

예제 입력 4

5 4 10
0 0 0 0 3
0 0 0 0 0
1 2 0 0 0
0 0 0 0 4
0 0 0 0 0
4 4 3 1
2 3 1 4
4 1 2 3
3 4 2 1
4 3 1 2
2 4 3 1
2 1 3 4
3 4 1 2
4 1 2 3
4 3 2 1
1 4 3 2
1 3 2 4
3 2 1 4
3 4 1 2
3 2 4 1
1 4 2 3
1 4 2 3

 

예제 출력 4

-1

 

✍🏻풀이

구현 문제이다. 구현 문제는 차근 차근 풀어야겠다..!

 

먼저, 각 위치의 정보를 저장하는 MapInfo 클래스와, 상어의 정보를 저장하는 Shark 클래스를 생성한다.

이후 MapInfo 이차원 배열을 사용해 문제를 풀 것이다. MapInfo 클래스는 (i, j) 자리의 정보를 갖고 있다. sharkNum은 해당 자리에 냄새를 뿌린 상어의 번호이고, smellTime은 상어의 냄새가 현재로부터 지속될 시간을 저장한다. 만약, (i, j) 위치의 sharkNum이 -1이고, smellTime이 0이라면 해당 자리에는 상어도 없고, 상어의 냄새도 남아있지 않은 것이다.

Shark 클래스는 상어의 위치인 x, y를 갖고, 상어의 방향인 dir를 갖는다. 또, 상어가 죽었는지(칸에서 나갔는지) 저장하는 dead 변수를 갖는다.

 

MapInfo[][] map은 위에서 설명한 것과 같이 (i, j) 자리의 정보를 갖는 이차원 배열이다.

int[][][] dirPriority는 각 상어들의 방향 우선순위를 저장하는 3차원 배열이다. dirPriority[1][3] = { 3, 1, 2, 0 }; 의 형태로 저장될 것인데, 이는 1번 상어가 오른쪽을 바라보고 있을 때의 방향 우선순위가 오른쪽(3), 아래(1), 왼쪽(2), 위(0)를 갖고있다는 것을 의미한다.

Shark[] sharks 배열은 각 상어의 정보를 저장하는 배열이다. sharks[1]에는 1번 상어의 정보가 저장되어 있다. sharks[1].x와 sharks[1].y는 1번 상어가 현재 위치하는 곳을 의미하고, sharks[1].dir은 현재 1번 상어가 바라보고 있는 방향이고, sharks[1].dead는 1번 상어가 죽었는지를 저장하는 변수이다.

 

이 변수들을 사용해서 문제대로 구현해주면 된다.

나는 상어가 이동하는 부분은 move() 메소드로, 상어들이 냄새를 칸에 뿌리는 건 smell() 메소드로 구현했다. move() 메소드 안에서 smell() 메소드를 호출하는 구조로 되어있다.

moveEnd() 메소드는 1번 상어만 남아있는 상태인지 확인하는 메소드로, moveEnd()가 true라면 상어를 그만 이동시키고, time을 출력하면 된다.

 

코드

package boj;

// 어른 상어 (https://www.acmicpc.net/problem/19237 )

import java.util.*;
import java.io.*;

public class BOJ_19237 {
	
	private static class MapInfo {
		private int sharkNum;
		private int smellTime;
		
		private MapInfo(int sharkNum, int smellTime) {
			this.sharkNum = sharkNum;
			this.smellTime = smellTime;
		}
	}
	
	private static class Shark {
		private int x;
		private int y;
		private int dir;
		private boolean dead;
		
		private Shark(int x, int y, boolean dead) {
			this.x = x;
			this.y = y;
		}
	}
	
	private static int N, M, k;
	private static int[] dx = { -1, 1, 0, 0 }; // 0, 1, 2, 3 = 위, 아래, 왼쪽, 오른쪽
	private static int[] dy = { 0, 0, -1, 1 }; // 0, 1, 2, 3 = 위, 아래, 왼쪽, 오른쪽
	private static MapInfo[][] map; // 상어들이 뿌리고 간 냄새의 정보를 저장, map[i][j].sharkNum = -1이고, map[i][j].smellTime = 0이면, 해당 위치에는 상어 냄새가 없다는 뜻
	private static int[][][] dirPriority; // 각 상어들의 방향 우선순위 저장, sharks[i][0]에는 i번 상어가 위를 향할 때의 우선순위를 갖고 있다.
	private static Shark[] sharks; // 상어들의 위치와 방향을 저장, sharks[i]에는 i번 상어의 정보가 담겨있다.

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		map = new MapInfo[N][N];
		dirPriority = new int[M + 1][4][4];
		sharks = new Shark[M + 1];
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			
			for (int j = 0; j < N; j++) {
				int cur = Integer.parseInt(st.nextToken());
				
				if (cur == 0) map[i][j] = new MapInfo(-1, 0);
				else {
					map[i][j] = new MapInfo(cur, k);
					sharks[cur] = new Shark(i, j, false);
				}
			}
		}
		
		st = new StringTokenizer(br.readLine());
		for (int sharkNum = 1; sharkNum <= M; sharkNum++) {
			sharks[sharkNum].dir = Integer.parseInt(st.nextToken()) - 1;
		}
		
		for (int i = 0, sharkNum = 1; i < M * 4; i++) {
			st = new StringTokenizer(br.readLine());
			for (int dir = 0; dir < 4; dir++) {
				dirPriority[sharkNum][i % 4][dir] = Integer.parseInt(st.nextToken()) - 1;
			}
			
			if (i % 4 == 3) sharkNum++;
		}
		
		int time = 0;
		while (time <= 1001) {
			time++;
			move();
			if (moveEnd()) break;
		}
		
		bw.write(time > 1000 ? "-1" : time + "");
		
		bw.flush();
		bw.close();
	}
	
	// 1. 이동(1초마다) & 방금 이동한 방향으로 상어의 방향 바꿔주기 & 냄새를 칸에 뿌린다. & 1초 이동했으므로, 냄새 -1
	private static void move() {
		MapInfo[][] newMap = new MapInfo[N][N];
		
		for (int sharkNum = 1; sharkNum <= M; sharkNum++) { // 각 상어마다 이동
			if (sharks[sharkNum].dead) continue; // 이미 죽은 상어는 이동시킬 필요가 없다.
			
			// 이동 방향 결정
			boolean decided = false;
			// 1. 인접한 칸 중, 아무 냄새가 없는 칸의 방향
			for (int dir = 0; dir < 4; dir++) {
				int curDir = dirPriority[sharkNum][sharks[sharkNum].dir][dir]; // sharksNum번 상어가 sharks[sharkNum].dir의 방향을 갖고 있고, 그 경우의 우선순위를 순서대로 가져온다.
				
				int nextX = sharks[sharkNum].x + dx[curDir];
				int nextY = sharks[sharkNum].y + dy[curDir];
				
				if (!validateScope(nextX, nextY)) continue;
				
				if (map[nextX][nextY].smellTime == 0) { // 찾았을 경우
					// 상어 이동
					// 만약, (nextX, nextY)에 이미 이동한 상어가 있을 경우에는 sharkNum이 작은 번호인 상어를 남기고 다 나간다.
					if (newMap[nextX][nextY] != null) {
						sharks[sharkNum].dead = true;// 현재 상어는 죽음
					}
					else { // 이미 이동한 상어가 없을 경우
						newMap[nextX][nextY] = new MapInfo(sharkNum, k);
						// i번째 상어의 위치와 방향을 이동한 값으로 바꾼다.
						sharks[sharkNum].x = nextX;
						sharks[sharkNum].y = nextY;
						sharks[sharkNum].dir = curDir;
					}
					decided = true;
					break;
				}
			}
			// 2. 그런 칸이 없으면, 자신의 냄새가 있는 칸의 방향
			if (!decided) {
				for (int dir = 0; dir < 4; dir++) {
					int curDir = dirPriority[sharkNum][sharks[sharkNum].dir][dir]; // sharksNum번 상어가 sharks[sharkNum].dir의 방향을 갖고 있고, 그 경우의 우선순위를 순서대로 가져온다.
					
					int nextX = sharks[sharkNum].x + dx[curDir];
					int nextY = sharks[sharkNum].y + dy[curDir];
					
					if (!validateScope(nextX, nextY)) continue;
					
					if (map[nextX][nextY].sharkNum == sharkNum) { // 자신의 냄새가 있는 방향 찾음
						// 상어 이동
						// 만약, (nextX, nextY)에 이미 이동한 상어가 있을 경우에는 sharkNum이 작은 번호인 상어를 남기고 다 나간다.
						if (newMap[nextX][nextY] != null) {
							sharks[sharkNum].dead = true;// 현재 상어는 죽음
						}
						else { // 이미 이동한 상어가 없을 경우
							newMap[nextX][nextY] = new MapInfo(sharkNum, k);
							// i번째 상어의 위치와 방향을 이동한 값으로 바꾼다.
							sharks[sharkNum].x = nextX;
							sharks[sharkNum].y = nextY;
							sharks[sharkNum].dir = curDir;
						}
						decided = true;
						break;
					}
				}
			}
		}
		
		smell(newMap);
	}
	
	
	private static void smell(MapInfo[][] newMap) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (newMap[i][j] != null) { // 상어가 새로 이동한 방향
					map[i][j].sharkNum = newMap[i][j].sharkNum;
					map[i][j].smellTime = k;
				}
				else { // 기존 방향
					if (map[i][j].smellTime > 1) map[i][j].smellTime--;
					else if (map[i][j].smellTime == 1) {
						map[i][j].sharkNum = -1;
						map[i][j].smellTime = 0;
					}
				}
			}
		}
	}
	
	private static boolean moveEnd() {
		boolean oneIsDead = sharks[1].dead;
		int aliveCnt = 0;
		for (int sharkNum = 1; sharkNum <= M; sharkNum++) {
			if (!sharks[sharkNum].dead) aliveCnt++;
		}
		
		if (!oneIsDead && aliveCnt == 1) return true;
		return false;
	}
	
	private static boolean validateScope(int x, int y) {
		if (x < 0 || x >= N || y < 0 || y >= N) return false;
		return true;
	}
}