[백준] 23290. 마법사 상어와 복제

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

23290번: 마법사 상어와 복제

---

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

public class Main {

	static int M, S, num = 1;
	static int SHARK = -1, SMELL = -2;
	static int[][] fishDir = { { 1, -1 }, { 0, -1 }, { -1, -1 }, { -1, 0 }, { -1, 1 }, { 0, 1 }, { 1, 1 }, { 1, 0 },
			{ 1, -1 } };
	static int[][] sharkDir = { { 0, 0 }, { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 } };
	static ArrayList<Fish> fishes = new ArrayList();
	static ArrayList<Fish> copyFishes = new ArrayList();
	static ArrayList<Integer>[][] map = new ArrayList[4][4], tempMap;
	static ArrayList<Integer>[][] smell = new ArrayList[4][4];
	static ArrayList<String> sharkDirArray = new ArrayList();

	static Fish Shark;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		M = Integer.parseInt(st.nextToken());
		S = Integer.parseInt(st.nextToken());

		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				map[i][j] = new ArrayList();
				smell[i][j] = new ArrayList();
			}
		}

		// 상어가 이동하는 배열 만들기 111, 112, 113, 121, 122...
		dfs(0, "");

		for (int i = 0; i <= M; i++) {
			st = new StringTokenizer(br.readLine());
			
			int fx = Integer.parseInt(st.nextToken()) - 1;
			int fy = Integer.parseInt(st.nextToken()) - 1;
			int fd = 0;
			
			if(i != M) fd = Integer.parseInt(st.nextToken());

			if (i == M) {
				Shark = new Fish(fx, fy, 0);
//				map[fx][fy].add(SHARK);
			} else {
				fishes.add(new Fish(fx, fy, fd));
				map[fx][fy].add(fd);
			}
		}

		for (int tc = 0; tc < S; tc++) {

			// 1. 복제 마법을 시전하기 위해 초기 물고기들 복사.
			copyFishes();

			// 2. 모든 물고기가 한 칸 이동한다.
			moveFishes();
//			print(map);

			// 3. 상어가 연속해서 3칸 이동한다.
			moveShark();
			
			// 4. 두 번 전 연습에서 생긴 물고기의 냄새를 격자에서 없앤다.
			removeSmell();
			
			// 5. 복제마법이 완료된다.
			magic();
			
//			System.out.println("끝");
//			System.out.println("상어 위치 : " + Shark.x + " " + Shark.y);
//			print(map);
//			print(smell);
			
			copyFishes.clear();
		}
		
		int answer = 0;
		
		// 격자에 남은 물고기수를 구한다.
		for(int i=0; i<4; i++) {
			for(int j=0; j<4; j++) {
				if(map[i][j].size() != 0)
					answer += map[i][j].size();
			}
		}
		
		System.out.println(answer);
	}
	
	public static void print(ArrayList[][] a) {
		for(int i=0; i<a.length; i++) {
			for(int j=0; j<a[i].length; j++) {
				if(a[i][j].size() == 0) {
					System.out.printf("%-8d", 0);
				} else {
					String tmp="";
					for(int k=0; k<a[i][j].size(); k++) {
						tmp += String.valueOf(a[i][j].get(k)) + ",";
					}
					System.out.printf("%-8s", tmp);
				}
			}
			System.out.println();
		}
		System.out.println();
	}
	
	public static void magic() {
		
		for(Fish f : copyFishes) {
			map[f.x][f.y].add(f.d); 
		}
	}
	
	
	public static void copyFishes() {
		for(int i=0; i<4; i++) {
			for(int j=0; j<4; j++) {
				if(map[i][j].size() != 0) {
					for(int k=0; k<map[i][j].size(); k++) {
						int n = map[i][j].get(k);
						copyFishes.add(new Fish(i, j, n));
					}
					
				}
			}
		}
	}
	
	public static void removeSmell() {
		for(int i=0; i<4; i++) {
			for(int j=0; j<4; j++) {
				if(smell[i][j].size() != 0) {
					for(int k=0; k<smell[i][j].size(); k++) {
						int time = smell[i][j].get(k);
						time -= 1;
						if(time != 0) {
							smell[i][j].set(k, time);
						} else {
							smell[i][j].remove(k);
							k--;
						}
					}
				}
			}
		}
//		print(smell);
	}

	public static void moveShark() {

		// 상어가 이동할 수 있는 모든 경우의수
		ArrayList<Dict> list = new ArrayList();
		
//		System.out.println("바뀌기 전 상어 위치 : " + Shark.x + " " + Shark.y);
		
//		print(map);
		
		for (String s : sharkDirArray) {
			
			tempMap = new ArrayList[4][4];
			
			for(int i=0; i<4; i++) {
				for(int j=0; j<4; j++) {
					tempMap[i][j] = new ArrayList();
				}
			}
			
			for(int i=0; i<4; i++) {
				for(int j=0; j<4; j++) {
					for(int k=0; k<map[i][j].size(); k++) {
						tempMap[i][j].add(map[i][j].get(k));
					}
				}
			}
			
			int nx = Shark.x;
			int ny = Shark.y;
			int nd = 0;
			int cnt = 0;
			boolean flag = false;
			
			for (int i = 0; i < s.length(); i++) {
				nd = (s.charAt(i)-48);
				nx += sharkDir[nd][0];
				ny += sharkDir[nd][1];
				
				// 범위안에 있고, 물고기가 있는 칸이면
				if(isInside(nx, ny)) {
					flag = true;
					cnt += tempMap[nx][ny].size();
					tempMap[nx][ny].clear();
					
				} else {
					flag = false;
					break;
				}
			}
			
			if(flag) {
				list.add(new Dict(s, cnt));
			}
		}
		
		// 상어가 이동할 방향을 정하고, 움직인다.
		Collections.sort(list);
		
		String select = list.get(0).direct;
		
//		System.out.println("선택된 상어 이동경로 : " + select);
		
//		print(map);
		
		for(int i=0; i<select.length(); i++) {
			
			Shark.d = select.charAt(i)-48;
			Shark.x += sharkDir[Shark.d][0];
			Shark.y += sharkDir[Shark.d][1];
			 
			// 물고기가있는 칸으로 이동하면 물고기는 격자에서 제외된다.
			if(map[Shark.x][Shark.y].size() != 0) {
				map[Shark.x][Shark.y].clear();
				smell[Shark.x][Shark.y].add(3);
			}
		}
		
//		print(map);
		
//		System.out.println("바뀌기 후 상어 위치 : " + Shark.x + " " + Shark.y);
//		print(smell);
	}

	public static void moveFishes() {

		tempMap = new ArrayList[4][4];
		
		for(int i=0; i<4; i++) {
			for(int j=0; j<4; j++) {
				tempMap[i][j] = new ArrayList();
			}
		}
		
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				if(map[i][j].size() != 0) {
					
					for (int d : map[i][j]) {
						
						for (int k = 0; k <= 8; k++) {
							int nd = (d-k) <= 0 ? d-k+8 : d-k;
							int nx = i + fishDir[nd][0];
							int ny = j + fishDir[nd][1];
							
							
							// 이 조건문이 중요 했음. 이동할 수 있는 칸이 없으면 이동을 하지 않는다.
							if(k == 8) {
								tempMap[i][j].add(d);
								break;
							}
							if(nx == Shark.x && ny == Shark.y) continue;
							if (isInside(nx, ny) && (smell[nx][ny].size() == 0)) {
								tempMap[nx][ny].add(nd);
								break;
							}
						}
					}
				}
			}
		}
		
		map = tempMap;
	}

	public static boolean isInside(int x, int y) {
		return x >= 0 && y >= 0 && x < 4 && y < 4;
	}

	public static void dfs(int depth, String st) {
		if (depth == 3) {
			sharkDirArray.add(st);
			return;
		}

		for (int i = 1; i <= 4; i++) {
			st += String.valueOf(i);
			dfs(depth + 1, st);
			st = st.substring(0, depth);
		}
	}

	static class Fish {
		int x;
		int y;
		int d;

		Fish(int x, int y, int d) {
			this.x = x;
			this.y = y;
			this.d = d;
		}

	}
	
	static class Dict implements Comparable<Dict>{
		String direct;
		int cnt;
		
		Dict(String direct, int cnt){
			this.direct=direct;
			this.cnt=cnt;
		}
		
		// cnt 내림차순, direct 오름차순
		@Override
		public int compareTo(Dict o) {
			if(this.cnt == o.cnt) {
				return this.direct.compareTo(o.direct);
			}
			return Integer.compare(o.cnt, this.cnt);
		}
	}
}