문제

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

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

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

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

이 과정을 반복할 때, 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을 출력한다.

코드

상어의 위치, 냄새, 방향 등 구현할 요소가 많은 문제였다.

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

public class Main_BOJ_19237_어른상어 {
	//입력값 N,M,k, 각 위치의 상어 수, 각 상어의 우선순위 방향, 현재 시간
	static int N,M,k,count[][],direction[],answer;
	//상, 하, 좌, 우
	static int[]dx = {0,-1,1,0,0};
	static int[]dy = {0,0,0,-1,1};
	//냄새를 저장 [상어 번호, 남은 시간]
	static int[][][]smell;
	//상어 정보 저장
	static Shake[] shakes;
	
	public static void main(String[] args)throws Exception {
		input();
		solve();
		if(answer>1000)System.out.println(-1);
		else System.out.println(answer);
	}
	
	static class Shake{
		//상어 번호
		int num;
		//현재 위치
		int pos[];
		//이동 우선순위
		int[][] priority;
		//초기화
		Shake(int num){
			this.num = num;
			this.pos = new int[2];
			this.priority = new int[5][4];
		}
		//위치 저장
		void setPos(int x,int y) {
			this.pos[0]=x;
			this.pos[1]=y;
		}
		//우선순위 저장
		void setPriority(int count,int[]priority) {
			System.arraycopy(priority, 0, this.priority[count], 0, 4);
		}
	}
	static void solve() {
		while(answer++<=1000) {
			setSmell();
			moveShake();
			removeShake();
			//남은 상어가 1마리면 종료
			if(M==1)break;
			removeSmell();
		}
	}
	//상어 이동
	static void moveShake() {
		for(Shake shake:shakes) {
			if(shake!=null) {
				int d = direction[shake.num],x=shake.pos[0],y=shake.pos[1],nextD=-1;
				for(int i=0;i<4;i++) {
					int nx = x + dx[shake.priority[d][i]];
					int ny = y + dy[shake.priority[d][i]];
					if(nx<0||ny<0||nx>=N||ny>=N)continue;
					//냄새가 없는 곳은 찾은 경우
					if(smell[nx][ny][0]==0) {
						nextD=i;
						break;
					}
					//본인의 냄새인 경우
					else if(smell[nx][ny][0]==shake.num&&nextD==-1)nextD=i;
				}
				if(nextD==-1)continue;
				//상어 이동
				int nx = x + dx[shake.priority[d][nextD]];
				int ny = y + dy[shake.priority[d][nextD]];
				shake.setPos(nx, ny);
				count[x][y]--;
				count[nx][ny]++;
				direction[shake.num]=shake.priority[d][nextD];
			}
		}
	}
	//상어 제거
	static void removeShake() {
		PriorityQueue<Integer>q = new PriorityQueue<>();
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				//현재 위치에 상어가 2마리 이상인 경우
				if(count[i][j]>1) {
					int now = 0;
					for(Shake shake:shakes) {
						if(shake==null)continue;
						if(shake.pos[0]!=i||shake.pos[1]!=j)continue;
						q.add(shake.num);
						if(++now==count[i][j])break;
					}
					count[i][j]=1;
					//상어 번호가 가장 낮은 상어 생존
					q.poll();
					//나머지 상어 제거
					while(!q.isEmpty()) {
						int num = q.poll();
						shakes[num] = null;
						M--;
					}
				}
			}
		}
	}
	//냄새 제거
	static void removeSmell() {
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				if(smell[i][j][0]!=0) {
					smell[i][j][1]--;
					//k초가 흐른 경우 냄새 제거
					if(smell[i][j][1]==0)smell[i][j][0]=0;
				}
			}
		}
	}
	//냄새 생성
	static void setSmell() {
		for(Shake shake:shakes) {
			if(shake!=null) {
				int x=shake.pos[0],y=shake.pos[1];
				smell[x][y][0]=shake.num;
				smell[x][y][1]=k;
			}
		}
	}
	//입력
	static void input() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		count = new int[N][N];
		smell = new int[N][N][2];
		direction = new int[M+1];
		shakes = new Shake[M+1];
		for(int i=1;i<=M;i++) {
			shakes[i]=new Shake(i);
		}
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<N;j++) {
				count[i][j]=Integer.parseInt(st.nextToken());
				if(count[i][j]!=0) {
					shakes[count[i][j]].setPos(i, j);
					count[i][j]=1;
				}
			}
		}
		st = new StringTokenizer(br.readLine());
		for(int i=1;i<=M;i++)direction[i]=Integer.parseInt(st.nextToken());
		for(int i=1;i<=M;i++) {
			for(int j=1;j<=4;j++) {
				st = new StringTokenizer(br.readLine());
				int[]tmp = new int[4];
				for(int k=0;k<4;k++)tmp[k]=Integer.parseInt(st.nextToken());
				shakes[i].setPriority(j, tmp);
			}
		}
	}
}