[BJ] 19237. 어른 상어

www.acmicpc.net/problem/19237

19237번: 어른 상어

✔ 문제 조건

1. N*N 크기 격자, M마리 상어
2. 모든 상어는 자신의 위치에 냄새를 뿌린 후
   1초마다 상하좌우로 이동하며 냄새를 뿌린다.
   냄새는 상어가 k번 이동하고 나면 사라진다.
3. 이동방향 결정
   1) 상하좌우 냄새가 없는 칸
   2) 그러한 칸이 없으면 상하좌우 자신의 냄새가 있는 칸
   3) 가능한 칸이 여러 개: 특정 우선순위를 따른다.
   우선순위는 상어마다 / 상어의 현재 방향마다 다르다.
4. 한 칸에 여러 마리의 상어가 남아 있으면 가장 작은 번호 상어만 남고 모두 쫓겨난다.
5. 1번 상어만 격자에 남게 되기까지 몇 초가 걸리는지

✔ 접근 과정

1. 상어 위치를 저장하는 2차원 배열 생성 -> sharkMap
   {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}
   
   
2. 각 칸의 냄새 정보를 저장하는 3차원 배열 생성 -> smellMap
   {{상어번호, k}, {상어번호, k}, {상어번호, k}, {상어번호, k}, {상어번호, k}}
   {{상어번호, k}, {상어번호, k}, {상어번호, k}, {상어번호, k}, {상어번호, k}}
   {{상어번호, k}, {상어번호, k}, {상어번호, k}, {상어번호, k}, {상어번호, k}}
   {{상어번호, k}, {상어번호, k}, {상어번호, k}, {상어번호, k}, {상어번호, k}}
   {{상어번호, k}, {상어번호, k}, {상어번호, k}, {상어번호, k}, {상어번호, k}}
   
   
3. 각 상어의 회전 우선 순위 정보 3차원 배열 생성 -> order
4. 상어의 현재 방향을 저장하는 1차원 배열 생성 -> dir
5. sharMap을 탐색하며, k를 -1하며 k초 이상 지난 냄새는 사라지게 한다. -> updateSmell()
   상어의 새 위치에 냄새 추가
   
   
6. sharkMap을 탐색하며, 상어가 있는 칸은 -> move()
   상하좌우로 1) 냄새가 없는 칸을 찾고 2) 그러한 칸이 없으면 자신의 냄새 칸을 찾는다.
   이때 기존의 sharMap을 이용하지 않고 새 배열을 만들어서 return 하고 갱신하는 방식으로 한다.
   왜냐하면, 이동할 칸에 아직 상어가 있더라도, 그 상어 차례가 지나고 나면 비게 될 칸이기 때문에
   새로운 배열을 생성하여 이번 time에서 이미 들어온 상어가 있는지를 살펴보아야 한다.
7. 1번 상어만 남았는지 확인한다.-> check()
8. 4, 5, 6을 반복하며 time에 +1하며, 1000초가 지나면 -1을 반환한다. -> solve()

✔ 주의할 점

1. BFS가 아니다. 상어가 냄새를 뿌린 공간에서도 1초 뒤 상하좌우로 냄새가 퍼지는게 아니다.
2. 방향 우선순위는...

   지금 상어가 3번(←) 방향이고, 우선순위가 order[상어번호][3][] = {↑ ← ↓ → } 이라면:
  3번(←) 방향으로 움직여 본 후
  못움직인다면,
  다음 우선순위인 ↓ 방향으로 움직여야 한다는 소린줄 알았다..

 

  그러나 그게 아니라
  지금 상어가 3번(←) 방향이고, 우선순위가 order[상어번호][3][] = {↑ ← ↓ → } 이라면:
↑ ← ↓ → 순으로 시도해보는 것이었다.

 

3. 상어번호를 임의로 0부터 시작하게 지정한다면, 비어있는 칸과 구분할 수 없어서 안된다.

 

import java.io.*;
import java.util.*;
// 210414

public class Main_BJ_19237_어른상어 {
	static int N, M, K;
	static int[][] sharkMap;
	static int[][][] smellMap;
	static int[] dir;
	static int[][][] order;
	static int[] dr = {-1, 1, 0, 0}; // 0 위 1 아래 2 좌 4 우
	static int[] dc = {0, 0, -1, 1};
	
	static void updateSmell() {
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(smellMap[i][j][1] > 0) {
					smellMap[i][j][1] -= 1;
				}
				// 여기서 상어의 새 위치에 냄새 정보를 업데이트 하기 때문에
				// 상어를 움직일 때 같은 동작을 할 필요 없다.
				if(sharkMap[i][j]>0) {
					smellMap[i][j][0] = sharkMap[i][j];
					smellMap[i][j][1] = K;
				}
			}
		}
	}
	
	static int[][] move() {
		int shark;
		int r, c, d, nr, nc;
		boolean found=false;
		
		int[][] newSharMap = new int[N][N];
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if (sharkMap[i][j] > 0) {
					// 상어가 있는 칸
					
					// 1) 상하좌우 빈칸 탐색
					shark = sharkMap[i][j];
					r=i; c=j; d=dir[shark];
					found=false;
					for(int di=0; di<4; di++) {
						nr = r+dr[ order[shark][d][di] ];
						nc = c+dc[ order[shark][d][di] ];
						if(nr<0 || nr>=N || nc<0 || nc>=N) continue;

						if(smellMap[nr][nc][1]==0) { // 냄새x
							if(newSharMap[nr][nc]==0) { // 아직 다른 상어가 안옴
								newSharMap[nr][nc]= shark;
								dir[shark] = order[shark][d][di];
								found = true;
								break;
							}
								
							else  {
								// 냄새는 아직 없지만 이미 다른 상어가 들어옴
								newSharMap[nr][nc]= Math.min(shark, newSharMap[nr][nc]);
								dir[shark] = order[shark][d][di];
								found = true;
								break;
							}	
						}
						
					} // 
					
					// 2) 상하좌우 자신의 냄새 칸 탐색
					if(found) continue;
					
					for(int di=0; di<4; di++) {
						nr = r+dr[ order[shark][d][di] ];
						nc = c+dc[ order[shark][d][di] ];
						if(nr<0 || nr>=N || nc<0 || nc>=N) continue;
						if(smellMap[nr][nc][0] == shark) {
							// 자신과 같은 냄새 칸
							dir[shark] = order[shark][d][di];
							newSharMap[nr][nc]= shark;
							break;
						}
					} // for
				}
			}
		}
		return newSharMap;
	}
	
	static boolean check( ) {
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(sharkMap[i][j]>1) return false;
			}
		}
		return true;
	}
	
	static int solve() {
		int time = 0;
		
		while(true) {
			updateSmell();
			sharkMap = move();
			++time;
			if(check()) return time;
			if(time>=1000) return -1;
		}
	}
	
	public static void main(String[] args) throws Exception {
		//System.setIn(new FileInputStream("res/input_BJ_19237_어른상어.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		N = stoi(st.nextToken());
		M = stoi(st.nextToken());
		K = stoi(st.nextToken());
		sharkMap = new int[N][N];
		smellMap = new int[N][N][N]; // 세번째: {상어번호, k}
		dir = new int[M+1];
		order = new int[M+1][4][4]; // 상어를 0번부터 시작하면 빈칸과 구분x, 방향 정보는 -1하여 저장
		
		// 상어 정보 & 냄새 정보
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j=0; j<N; j++) {
				sharkMap[i][j] = stoi(st.nextToken());
				if(sharkMap[i][j]>0) {
					smellMap[i][j][0] = sharkMap[i][j];
					smellMap[i][j][0] = K;
				}
			}
		}

		// 현재 상어 방향
		st = new StringTokenizer(br.readLine(), " ");
		for(int i=1; i<=M; i++) {
			dir[i] = stoi(st.nextToken())-1;
		}
		
		// 상어 별 이동 우선순위
		for(int i=1; i<=M; i++) {
			for(int j=0; j<4; j++) {
				st = new StringTokenizer(br.readLine(), " ");
				for(int z=0; z<4; z++) {
					order[i][j][z] = stoi(st.nextToken())-1;
				}
			}
		}
		
		System.out.println(solve());

		br.close();
	}
	
	static int stoi(String str) {
		return Integer.parseInt(str);
	}
}

 

코드 참조 (언어만 다르고 거의 비슷함) : github.com/ndb796/python-for-coding-test/blob/master/19/3.py