[백준/boj] 23290: 마법사 상어와 복제 (JAVA) / 구현 / DFS

문제

23290번: 마법사 상어와 복제

풀이

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

public class Main {
	static int minNum; // 상어 이동 방향 사전순 제일 높은것 (숫자가 낮은)
	static int maxFishNum; // 상어가 가장 많이 먹을 수 있는 물고기 수
	static ArrayList<Fish>[][] map;
	static int[][] smellMap;
	static ArrayList<Fish> copyFish;
	static int[] dx = {0, 0, -1, -1, -1, 0, 1, 1, 1}; // 좌부터 시계방향 
	static int[] dy = {0, -1, -1, 0, 1, 1, 1, 0, -1};
	static int[] sx = {0, -1, 0, 1, 0}; // 상 좌 하 우 
	static int[] sy = {0, 0, -1, 0, 1};
	static Shark shark;
	static int[][] fishCntMap; // dfs 때 상어가 먹는 물고기 수를 세기 위한 맵
	
	static class Fish {
		int x;
		int y; 
		int d;
		boolean isMoved;
		
		Fish(int x, int y, int d, boolean isMoved) {
			this.x = x;
			this.y = y;
			this.d = d;
			this.isMoved = isMoved;
		}
	}
	
	static class Shark {
		int x;
		int y;
		
		Shark(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int M = Integer.parseInt(st.nextToken()); // 물고기 수 
		int S = Integer.parseInt(st.nextToken()); // 마법 횟수
		map = new ArrayList[4][4];
		for(int i=0; i<4; i++)
			for(int j=0; j<4; j++)
				map[i][j] = new ArrayList<Fish>();
		copyFish = new ArrayList<Fish>();
		smellMap = new int[4][4];
		minNum = Integer.MAX_VALUE;
		maxFishNum = 0;
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken()) -1;
			int y = Integer.parseInt(st.nextToken()) -1;
			int d = Integer.parseInt(st.nextToken());
			map[x][y].add(new Fish(x, y, d, false));
		}
		st = new StringTokenizer(br.readLine());
		int sx = Integer.parseInt(st.nextToken()) - 1;
		int sy = Integer.parseInt(st.nextToken()) - 1;
		shark = new Shark(sx, sy);
		
		while(S > 0) {
			// 1. 복제
			copy();
			// 2. 물고기 이동
			for(int i=0; i<4; i++) {
				for(int j=0; j<4; j++) {
					if(map[i][j].size() > 0) moveFish(i, j, map[i][j].size());
				}
			}
			// 3. 상어 이동
			moveShark();
			minNum = Integer.MAX_VALUE;
			maxFishNum = 0;
			// 4. 물고기 냄새 줄이기 
			reduceFishSmell();
			// 5. 복제 나타나기
			magic();
			S--;
		}
		System.out.println(getFishNum());
	}

	private static int getFishNum() {
		int cnt = 0;
		for(int i=0; i<4; i++) {
			for(int j=0; j<4; j++) {
				cnt += map[i][j].size();
			}
		}
		return cnt;
	}

	private static void magic() {
		for(Fish fish : copyFish) {
			map[fish.x][fish.y].add(fish);
		}
	}

	private static void moveShark() {
		fishCntMap = new int[4][4];
		copyFishCnt();
		dfs(0, 0, 0, shark.x, shark.y);
		for(int i=2;i >= 0; i--) {
			int dir = minNum / (int) Math.pow(10, i);
			minNum -= (int) Math.pow(10, i) * dir;
			int x = shark.x; int y  = shark.y;
			int nx = x + sx[dir];
			int ny = y + sy[dir];
			shark.x = nx;
			shark.y = ny;
			for(int c = map[nx][ny].size() -1; c >= 0; c--) {
				map[nx][ny].remove(c);
				smellMap[nx][ny] = 3;
			}
		}
	}

	private static void copyFishCnt() {
		for(int i=0; i<4; i++) {
			for(int j=0; j<4; j++) {
				fishCntMap[i][j] = map[i][j].size();
			}
		}
		
	}

	private static void dfs(int dir, int cnt, int fishNum, int x, int y) {
		if(cnt == 3) {
			if(maxFishNum > fishNum) return;
			if(maxFishNum == fishNum && minNum < dir) return;
			maxFishNum = fishNum;
			minNum = dir;
			return;
		}
	
		for(int i=1; i<=4; i++) {
			int newDir = (int) (dir + Math.pow(10, 2-cnt) * i);
			int nx = x + sx[i];
			int ny = y + sy[i];
			if(!isRange(nx, ny)) continue;
			int tempCnt = fishCntMap[nx][ny];
			int newFishNum = fishNum + fishCntMap[nx][ny];
			fishCntMap[nx][ny] = 0;
			dfs(newDir, cnt +1, newFishNum, nx, ny);
			fishCntMap[nx][ny] = tempCnt;
		}
	}

	private static void reduceFishSmell() {
		for(int i=0; i<4; i++) {
			for(int j=0; j<4; j++) {
				if(smellMap[i][j] > 0) smellMap[i][j]--; 
			}
		}
	}

	private static void moveFish(int mx, int my, int cnt) {
		int nx, ny;
		for(int c = cnt - 1; c >= 0; c--) {
			Fish fish = map[mx][my].get(c);
			if(fish.isMoved) continue;
			int oriD = fish.d;
			int d = fish.d;
			int x = fish.x;
			int y = fish.y;
			nx = x + dx[d];
			ny = y + dy[d];
			boolean dontMoveFlag = false;
			while(!canMove(nx, ny)) {
				d -= 1;
				if(d == 0) d = 8;
				if(d == oriD) { // 이동할 수 있는 방향이 없음
					dontMoveFlag = true; 
					break;
				}
				nx = x + dx[d];
				ny = y + dy[d];
			}
			if(dontMoveFlag) continue; 
			// 이동
			map[mx][my].remove(c);
			map[nx][ny].add(new Fish(nx, ny, d, true));
		}
	}

	private static boolean canMove(int x, int y) {
		// 상어, 물고기 냄새, 격자범위 check 
		return (x == shark.x && y == shark.y) || !isRange(x, y) || smellMap[x][y] > 0 ? false : true; 
	}

	private static void copy() {
		copyFish.clear();
		for(int i=0; i<4; i++) {
			for(int j=0; j<4; j++) {
				int cnt = map[i][j].size();
				for(int c=0; c<cnt; c++) {
					copyFish.add(map[i][j].get(c));
					map[i][j].get(c).isMoved = false;
				}
 			}
		}
	}
	
	private static boolean isRange(int x, int y) {
		return x >= 4 || x < 0 || y >= 4 || y < 0 ? false : true;
	}
}