[JAVA] BOJ 백준 19237 어른 상어

https://www.acmicpc.net/problem/19237

19237번: 어른 상어

문제

청소년 상어는 더욱 자라 어른 상어가 되었다. 상어가 사는 공간에 더 이상 물고기는 오지 않고 다른 상어들만이 남아있다. 상어에는 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초마다 상어들은 다음과 같은 행동을 반복한다.

1. 상하좌우 인접한 칸으로 “동시에” 이동한다.
2. 도착한 칸에 냄새를 뿌린다.
3. 냄새는 k번 이동하면 사라진다.
4. 모든 상어가 이동 후 한 칸에 있는 상어는 가장 숫자가 작은 상어(강한 상어)이다.

이때 이동 위치을 결정하는 것은 다음과 같다.

1. 아무 냄새 없는 곳
2. 자신의 냄새가 있는 곳

같은 우선 순위를 가진 곳은 하나가 아닐수 있는데 이때는 특정한 방향 우선순위로 결정한다. 우선순위는 상어마다 다르다.

1번 상어만 격자에 남을 때까지 몇초가 걸리는지 구하자!

전체 코드

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

public class Main {
	static int N, M ;
	static int t, k;
	static int[][] water;
	static int[][][] dir;
	static int[][][] smell;
	static int[] D;
	static int[] dx = {0, -1, 1, 0, 0};
	static int[] dy = {0, 0, 0, -1, 1};
	public static void main(String[] args) throws Exception {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
		StringBuilder sb = new StringBuilder();
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		water = new int[N][N];
		smell = new int[N][N][2];
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(bf.readLine(), " ");
			for(int j=0; j<N; j++) {
				water[i][j] = Integer.parseInt(st.nextToken());
				if(water[i][j] > 0) {smell[i][j][0] = water[i][j]; smell[i][j][1] = k;}
			}
		}
		D = new int[M+1];
		st = new StringTokenizer(bf.readLine(), " ");
		for(int i = 1; i<=M; i++)
			D[i] = Integer.parseInt(st.nextToken());
		
		dir = new int[M+1][5][5];
		for(int i=1; i<=M; i++) {
			for(int d = 1; d<=4; d++) {
				st = new StringTokenizer(bf.readLine(), " ");
				for(int u=1; u<=4; u++)
					dir[i][d][u] = Integer.parseInt(st.nextToken());
			}
		}
		for(t=1; t<=1001; t++) {
			if(t == 1001) break;
			move();
			if(M == 1) break;
		}
		if(t == 1001) t = -1;
		System.out.println(t);
	}
	static void move() {
		int[][] tmp = new int[N][N];
		ArrayDeque<int[]> newsmell = new ArrayDeque<>();
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(water[i][j] == 0) continue;
				int s = water[i][j]; int mx = N; int my = N; int md = 0;
				for(int d = 1; d<=4; d++) {
					int ni = i + dx[dir[s][D[s]][d]];
					int nj = j + dy[dir[s][D[s]][d]];
					if(ni < 0 || nj < 0 || ni >= N || nj >= N) continue;
					if(smell[ni][nj][0] != s && smell[ni][nj][1] >= t) continue;
					if(smell[ni][nj][1] < t) {mx = ni; my = nj; md = dir[s][D[s]][d]; break;} // 최적을 찾았으므로 나가도 됨
					else if(smell[ni][nj][0] == s && mx == N) // mx가 아무 선택도 안된 경우 -> 가장 처음에 선택된 방향이 됨
						{mx = ni; my = nj; md = dir[s][D[s]][d];}
				}
				if(tmp[mx][my] == 0) {tmp[mx][my] = water[i][j]; newsmell.offer(new int[] {mx, my, s, t+k});}
				else if(tmp[mx][my] > water[i][j]) {tmp[mx][my] = water[i][j]; M--; newsmell.offer(new int[] {mx, my, s, t+k});}
				else {M--;}
				D[s] = md;
			}
		}
		while(!newsmell.isEmpty()) {
			int[] n = newsmell.poll();
			smell[n[0]][n[1]][0] = n[2];
			smell[n[0]][n[1]][1] = n[3];
		}
		water = tmp;
	}
}

한줄씩 살펴보자

static int N, M ;
static int t, k;
static int[][] water;
static int[][][] dir;
static int[][][] smell;
static int[] D;
static int[] dx = {0, -1, 1, 0, 0};
static int[] dy = {0, 0, 0, -1, 1};

N, M, k, water는 입력받은 값을 저장하는 변수이다.

t는 현재까지 흐른 초를 나타낸다.

dir는 어른 상어들의 방향 우선순위 정보를 나타낸다.

예를 들어 dir[1][1][1] : 1번 상어가 현재 바라보는 방향이 1일 때 최고 우선순위(1위)

smell은 해당 위치의 냄새의 주인과 냄새를 남긴 시간 + k를 저장한다.

이렇게 하면 현재로 부터 k초 후부터 이 위치로 이동이 가능하다.

받는 정보의 방향은 1~4이므로 바로 사용할 수 있도록 0에는 정보를 주지 않았다.

D에는 상어들의 현재 바라보는 방향을 저장해준다.

for(int i=0; i<N; i++) {
		st = new StringTokenizer(bf.readLine(), " ");
		for(int j=0; j<N; j++) {
			water[i][j] = Integer.parseInt(st.nextToken());
			if(water[i][j] > 0) {smell[i][j][0] = water[i][j]; smell[i][j][1] = k;}
		}
	}

처음 시작하는 위치에도 냄새를 뿌리기 때문에 입력과 동시에 smell에 정보를 저장한다.

dir = new int[M+1][5][5];
	for(int i=1; i<=M; i++) {
		for(int d = 1; d<=4; d++) {
			st = new StringTokenizer(bf.readLine(), " ");
			for(int u=1; u<=4; u++)
				dir[i][d][u] = Integer.parseInt(st.nextToken());
		}
	}
	for(t=1; t<=1001; t++) {
		if(t == 1001) break;
		move();
		if(M == 1) break;
	}
	if(t == 1001) t = -1;

dir 변수에 상어의 이동 위치 우선순위를 저장해준다. 이때 방향은 1~4를 사용하기 때문에 5로 선언해준다.

1000초 이후 이동은 의미가 없기 때문에 1001에 for문을 종료한다. 이동이 불가능한 경우는 -1를 출력해준다.

int[][] tmp = new int[N][N];
	ArrayDeque<int[]> newsmell = new ArrayDeque<>();
	for(int i=0; i<N; i++) {
		for(int j=0; j<N; j++) {
			if(water[i][j] == 0) continue;
			int s = water[i][j]; int mx = N; int my = N; int md = 0;

move()는 상어를 이동시키는 함수이다. 이동된 위치와 현재 위치를 혼동하지 않도록 tmp를 선언해서 저장해줄 것이다.

새로운 냄새를 저장하기 위한 deque을 선언한다. 만약 바로 smell에 저장한다면 갱신된 smell 배열로 인해 동시에 이동하는 상어를 표현할 수 없게 된다.

예를들어 1번 상어가 (1, 2)로 이동하여 냄새를 남기면 2번 상어는 (1, 2)로 이동할 수 없게 된다.

상어가 있는 위치를 확인하고 s에 상어의 숫자를 저장해준다. mx, my, md를 통해 갱신되는 상어의 정보를 저장할 것이다.

for(int d = 1; d<=4; d++) {
		int ni = i + dx[dir[s][D[s]][d]];
		int nj = j + dy[dir[s][D[s]][d]];
		if(ni < 0 || nj < 0 || ni >= N || nj >= N) continue;
		if(smell[ni][nj][0] != s && smell[ni][nj][1] >= t) continue;
		if(smell[ni][nj][1] < t) {mx = ni; my = nj; md = dir[s][D[s]][d]; break;} // 최적을 찾았으므로 나가도 됨
		else if(smell[ni][nj][0] == s && mx == N) // mx가 아무 선택도 안된 경우 -> 가장 처음에 선택된 방향이 됨
			{mx = ni; my = nj; md = dir[s][D[s]][d];}
	}

4방향을 모두 탐색할 것이다. dir[s][D[s]][d] 에는 s번 상어의 현재 위치 (D[s])일 때 d번째 우선순위 방향이 담겨있다. 우선 순위 대로 탐색하고 격자를 벗어나거나 다른 상어의 냄새가 남아있는 경우 continue처리한다. 만약 냄새를 남긴 시간이 t보다 작다면 아무 냄새가 남아있지 않을 것이다. 그러므로 1순위로 이동가능한 곳이 된다. 바로 break를 해도 된다.

하지만 그러한 곳이 없는 경우 자신의 냄새가 있는 곳으로 이동해야 하므로 가장 먼저 만난 곳을 mx, my에 저장해준다.

		if(tmp[mx][my] == 0) {tmp[mx][my] = water[i][j]; newsmell.offer(new int[] {mx, my, s, t+k});}
		else if(tmp[mx][my] > water[i][j]) {tmp[mx][my] = water[i][j]; M--; newsmell.offer(new int[] {mx, my, s, t+k});}
		else {M--;}
		D[s] = md;
	}
}
while(!newsmell.isEmpty()) {
	int[] n = newsmell.poll();
	smell[n[0]][n[1]][0] = n[2];
	smell[n[0]][n[1]][1] = n[3];
}
water = tmp;

해당 위치에 상어가 없는 경우는 이동 가능하므로 이동해준다.

만약 해당 위치의 상어가 자신보다 큰 수를 가졌다면 이동가능하고 상어 한마리가 격자 밖으로 벗어나게 되기 때문에 M을 감소시킨다.

두 경우에 해당하지 않으면 격자 밖으로 나가야 되므로 또한 M을 감소한다.

이동이 모두 종료됐으므로 smell을 저장해준다. 굳이 격자에 다른 상어가 있는지 조사할 필요없이 들어온 순서대로 smell 배열에 저장해주어도 격자에 남은 상어의 것이 마지막에 들어왔기 때문에 괜찮다.

마지막으로 이동된 위치로 water를 변경한다.