[ 백준 / 19237 ] 어른상어 : java

Gold V 이후로 이제 난 못풀겠다 수준이다... 하나 하나 푸는데 너무 힘들어....

디버깅에만 얼마를 쏟는지...ㅜㅠㅜ 그래도 이번 문제는 테케만 맞으니 잘 풀어졌다... Gold 4라서 그런가..ㅠㅜ

문제

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

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

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

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

<그림 1>

우선 순위상어 1상어 2상어 3상어 4↑↑↑↑↓↓↓↓←←←←→→→→

↓ ← ↑ →	↓ → ← ↑	→ ← ↓ ↑	← → ↑ ↓
→ ↑ ↓ ←	↓ ↑ ← →	↑ → ← ↓	← ↓ → ↑
← → ↓ ↑	← → ↑ ↓	↑ ← ↓ →	↑ → ↓ ←
→ ← ↑ ↓	→ ↑ ↓ ←	← ↓ ↑ →	↑ → ↓ ←

<표 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을 출력한다.

먼저 풀이 코드를 첨부하고 문제에 대한 설명을 지속한다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 어른상어 {

	static int[] di = {0,-1,1,0,0};
	static int[] dj = {0,0,0,-1,1};
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		int [][][] arr =new int[N][N][2]; //상어, 냄새
		int [] si = new int[M+1];
		int [] sj = new int[M+1];
		for(int i = 0; i<N;i++) {
			st =new StringTokenizer(br.readLine());
			for(int j = 0; j< N;j++) {
				int a = Integer.parseInt(st.nextToken());
				arr[i][j][0] = a;
				if(a!=0) {
					si[a]= i;
					sj[a] = j;
					arr[i][j][1]=K;
				}
			}
		}
		// 현재 방향 
		int[] d = new int[M+1];
		st = new StringTokenizer(br.readLine());
		for(int i = 1; i<=M;i++) {
			d[i] = Integer.parseInt(st.nextToken());
		}
		// 이제 우선순위 상1,하2,좌3, 우4 
		int[][][] order = new int[M+1][5][4];
		for(int i = 1; i<=M;i++) {
			for(int j = 1; j<5;j++) {
				st = new StringTokenizer(br.readLine());
				for(int k = 0; k<4;k++) {
					order[i][j][k] =Integer.parseInt(st.nextToken()); 
				}
			}
		}
		int m = M; // 남은 상어 수 
		int time = 0; 
		while(m>1 && time <1001) {
			
//			System.out.println(Arrays.toString(d));
			
			
			// 작은 얘들부터 이동을 시킨다. 
			for(int s = M; s>0;s--) {
				if(si[s]<0)continue;
				int i = si[s];
				int j = sj[s];
				boolean flag = false;
				for(int a = 0; a<4;a++) {
					if(i+di[order[s][d[s]][a]]<0 ||  i+di[order[s][d[s]][a]]>N-1 ||j+dj[order[s][d[s]][a]]<0 || j+dj[order[s][d[s]][a]]>N-1 )
						continue;
					if(arr[i+di[order[s][d[s]][a]]][j+dj[order[s][d[s]][a]]][0]==0) {
						d[s] = order[s][d[s]][a];
						si[s]+=di[d[s]];
						sj[s]+=dj[d[s]];
						j = sj[s];
						i = si[s];
						flag = true;
						break;
					}
				}
				if(!flag) {
					for(int a = 0; a<4;a++) {
						if(i+di[order[s][d[s]][a]]<0 ||  i+di[order[s][d[s]][a]]>N-1 ||j+dj[order[s][d[s]][a]]<0 || j+dj[order[s][d[s]][a]]>N-1 )
							continue;
						if(arr[i+di[order[s][d[s]][a]]][j+dj[order[s][d[s]][a]]][0]==s) {
							d[s] = order[s][d[s]][a];
							si[s]+=di[d[s]];
							sj[s]+=dj[d[s]];
							break;
						}
					}
				}
			}// 이동완료
			// 먼저 시간이 지났으니 다 뺀다.
			for(int i = 0; i<N;i++) {
				for(int j = 0; j<N;j++) {
					if(arr[i][j][1]>1) {
						arr[i][j][1]--;
					}else if(arr[i][j][1]==1) {
						arr[i][j][1]=0;
						arr[i][j][0]=0;
					}
				}
			}
			for(int s = M;s>0;s--) { //자리 잡고 냄새 뿌리기
				if(si[s]<0)continue;
				int t;
				for(t = s-1; t>0;t--) {
					if(si[t]==si[s] && sj[t]==sj[s]) {
						si[s] = -s;
						sj[s]=-s;
						d[s] = 0; 
						m--;
						break;
					}
				}
				if(t==0) {
					arr[si[s]][sj[s]][0] = s;
					arr[si[s]][sj[s]][1] = K;
				}
			}
//			System.out.println(time);
			time++;
//			for(int i = 0; i<N;i++) {
//				for(int j = 0; j<N;j++) {
//					if(arr[i][j][0]==0) {
//						System.out.print('-');
//						if(arr[i][j][1]==0) {
//							System.out.print("-"+" ");
//						}
//					}else {
//						System.out.print(arr[i][j][0]+""+arr[i][j][1]+" ");
//					}
//					
//				}
//				System.out.println();
//			}
		}
		if(m!=1)System.out.println(-1);
		else System.out.println(time==1001?-1:time);
	}
}

 

 문제에서 여기에서 중요하게 볼 점은 

1. 우선순위가 모두 정해져 있다는 사실이다. bfs, dfs, 등을 이용할 필요 없이 while문에 의해서만 돌아가는 문제이다. 

시간 초과를 덜 신경쓰게 되는 문제 이다. ㄹㅇ 시뮬레이션의 정석 같은 문제!

2. 문제 이해가 오래 걸린다.  우선수위 배열이 전부 따로 있어서, 확인에 어려움을 겪는다.

3. 상어 냄새가 사라지는 시점, 움직이는 시점, 이 시점 차이들이 또 중요하게 작용한다. 

예시에 맞게 최대한 검사하면서 진행해야 한다. 

 

풀이.

1. 데이터 받아오기 

처음 상어들의 위치를 상어 번호와 냄새를 모두 저장할 수 있도록 3차원 배열로 받앗다. 여기에서 초기 냄새 설정 arr[i][j][1]=K까지 하고 돌게 된다. 

이후 들어오는 데이터는  현재 방향이다. 

현재 상어들이 바라보는 방향을 저장할 배열을 하나 더 지정해 준다. 

 

그리고 우선순위에 따라 이동할 수 있도록 상어를 저장해 준다. 방향에 맞추어, 0을 뺸 상어 번호와, 0을 뺸, 방향 1,2,3,4를 설정해 int[M+1][5][4] 로선언하였다. 

그리고 탈출 조건을 위하여 남은 상어의 수와, 시간의 초기값을 설정해 준다. 

 

2. 상어 이동 

먼저 하는 것은 상어의 이동이다. 

작은 애들부터 먼저 이동시켜 상어를 움직였다. 여기서 상어의 위치가 변경되게 된다. 앞의 for문은 냄새가 없는 우선순위 탐색을 하게 되고,

뒤의 flag가 false일 경우 실행되는 반복문은 주변에 갈 곳이 없을 때 자신의 냄새가 있는 곳으로 이동하기 위함이다. 

이제 이동완료를 한 다음에 냄새가 하나 사라져야 한다.

이전에 냄새의 시간을 먼저 빼고, 계산을 했었는데, 예시와 일치하지 않는 문제가 발생하여

이후로 수정하여 주었더니 성공하였다. 

 

3. 상어의 위치를 고정하고 냄새를 뿌린다. 

si와 sj의 배열에 상어의 위치가 저장되어 있는데, 이를 뒤에서 부터 확인하면서 

순환하게 되는데, 그럼 작은값의 상어만 남고, 큰값의 상어는 저장되지 않고, 마이너스의 값을 갖게 된다. 

그러면서 남은 상어의 개수와 시간을 확인하며 반복문을 돈다.

4. 결과 출력 

모든 반복문을 돌고, 남은 상어의 개수가 1이 아니거나 1001이 되게 되면, -1을 출력하고,

아닐 경우 걸린 시간을 출력하게 된다. 

 

 

복잡한 시뮬레이션의 정석 같은 느낌이다. 

풀고나니 Gold 2였던 구슬 어쩌고 보다는 쉬운 느낌이다.. 그래도 머리 아파...