[백준/boj] 19237: 어른 상어 (JAVA) / 구현 / 시뮬레이션

문제

19237번: 어른 상어

풀이

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

public class Main {
	static ArrayList<Shark>[][] map; // 상어의 위치 
	static ArrayList<Smell>[][] smellMap; // 상어의 냄새 정보
	static Map<Integer, int[][]> orders; // 상어의 이동 우선순위 <상어번호, 상하좌우에따른 이동순위 int[4]>
	static int N; // 격자 범위 
	static int M; // 상어 숫자 
	static int k; // 냄새가 사라지기까지의 횟수
	static int[] dx = {0, -1, 1, 0, 0}; // 상하좌우
	static int[] dy = {0, 0, 0, -1, 1}; 

	static class Shark {
		int sNum; // 상어 번호
		int x; 
		int y;
		int dir; // 현재 방향
		boolean isMoved; // 이동 여부
		
		Shark(int sNum, int x, int y, int dir, boolean isMoved) {
			this.sNum = sNum;
			this.x = x;
			this.y = y;
			this.dir = dir;
			this.isMoved = isMoved;
		}
	}
	
	static class Smell {
		int sNum; // 상어 번호
		int k; // 남은 횟수 
		
		Smell(int sNum, int k) {
			this.sNum = sNum;
			this.k = k;
		}
	}
	
	public static void main(String[] args) throws Exception {
		int answer = 0; // 1번 상어만 남기까지 걸리는 시간 
		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());
		map = new ArrayList[N][N];
		smellMap = new ArrayList[N][N];
		orders = new HashMap<>();
		List<Shark> sharks = new ArrayList<>();
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				map[i][j] = new ArrayList<>();
				smellMap[i][j] = new ArrayList<>();
				int sNum = Integer.parseInt(st.nextToken());
				if(sNum > 0) {
					sharks.add(new Shark(sNum, i, j, 0, false));
				}
			}
		}
		
		int[] tempDirs = new int[M+1];
		st = new StringTokenizer(br.readLine()); // 상어의 방향
		for(int i=1; i<=M; i++) {
			tempDirs[i] = Integer.parseInt(st.nextToken());
		}
		
		for(Shark shark: sharks) {
			shark.dir = tempDirs[shark.sNum];
			map[shark.x][shark.y].add(shark);
		}
		
		
		for(int i=1; i<=M; i++) { // 상어마다 			
			int[][] tempOrderArr = new int[5][5]; // 0~4
			for(int j=1; j<=4; j++) { // 방향에 따른 (상하좌우)
				st = new StringTokenizer(br.readLine());
				for(int k=1; k<=4; k++) { // 우선순위 4개 
					tempOrderArr[j][k] = Integer.parseInt(st.nextToken());
				}
			}
			orders.put(i, tempOrderArr);
		}
		
		while(remainSharkCnt() != 1) {
			answer++;
			if(answer > 1000) {
				answer = -1; break;
			}
			
			// 1. 이동하기  
			moveShark();
			// 2. 겹치는 상어 내쫓기 
			outShark();
			// 3. k 줄이기 
			reduceK();
		}
		
		System.out.println(answer);
	}

	private static void outShark() {
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				int minNum = Integer.MAX_VALUE;
				for(int s=map[i][j].size()-1; s>=0; s--) {
					minNum = Math.min(minNum , map[i][j].get(s).sNum); 
					map[i][j].get(s).isMoved = false;
				}
				
				for(int s=map[i][j].size()-1; s>=0; s--) {
					if(map[i][j].get(s).sNum != minNum) map[i][j].remove(s);
				}
			}
		}
	}

	private static void reduceK() {
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				for(int s=smellMap[i][j].size()-1; s>=0; s--) {
					Smell smell = smellMap[i][j].get(s);
					if(smell.k > 0) smell.k -= 1;
					if(smell.k == 0) smellMap[i][j].remove(s);
				}
			}
		}
	}

	private static void moveShark() {
		// 이동 
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				for(int s=map[i][j].size()-1; s>=0; s--) {
					Shark shark = map[i][j].get(s);
					if(shark.isMoved) continue;
					int nx; 
					int ny;
					// 우선순위 중 ! 인접한 칸 중 아무 냄새 없는 칸
					int[][] dirs = orders.get(shark.sNum);
					for(int dir : dirs[shark.dir]) {
						if(dir == 0) continue;
						nx = shark.x + dx[dir];
						ny = shark.y + dy[dir];
						if(!isRange(nx, ny) || smellMap[nx][ny].size() > 0) continue;
						shark.x = nx;
						shark.y = ny;
						shark.dir = dir;
						shark.isMoved = true;
						map[i][j].remove(s);
						map[nx][ny].add(shark);
						smellMap[i][j].add(new Smell(shark.sNum, k));
						break;
					}
					
					if(!shark.isMoved) { // 자신의 냄새가 있는 곳으로 
						bp: for(int dir : dirs[shark.dir]) {
							if(dir == 0) continue;
							nx = shark.x + dx[dir];
							ny = shark.y + dy[dir];
							if(!isRange(nx,ny)) continue;
							for(Smell smell : smellMap[nx][ny]) {
								if(smell.sNum == shark.sNum) {
									shark.x = nx;
									shark.y = ny;
									shark.dir = dir;
									shark.isMoved = true;
									map[i][j].remove(s);
									map[nx][ny].add(shark);
									smellMap[i][j].add(new Smell(shark.sNum, k));
									break bp;
								}
							}
						}
					}
				}
			}
		}
	}

	private static boolean isRange(int nx, int ny) {
		return nx >= N || nx <0 || ny >= N || ny <0 ? false: true;
	}

	private static int remainSharkCnt() {
		int cnt = 0; 
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(map[i][j].size() != 0) cnt+= map[i][j].size();
			}
		}
		return cnt;
	}
}