[Java/자바 백준 23290] 마법사 상어와 복제

풀이

문제를 읽다보면 주어진 조건이 너무 많다는 걸 알 수 있다..

 

우선 map 자체를 뭐로 선언해야할까 효율적일까 고민하다가

list로 선언하기에 삭제나 삽입할때 문제가 생길거 같아서

2차원 큐 형태로 물고기의 방향 값을 갖도록 설계했습니다.

 

1. copyFishmap() : 맵에 있는 물고기들 전부 복사하기 

map에 사이즈만큼 값을 copy[][]에  넣어줬습니다.

 

2. moveFish() : 물고기 이동

해당 맵 인덱스에 물고기가 있다면, 자신이 바라보는 방향부터 시작해서 반시계 45도로 탐색을 시작했습니다.

상어, 물고기 냄새, 격자 밖은 못가주게 해주었고 만약 8방향 탐색 후 모두 갈 수 없다면 제자리에 있도록 해주었습니다.

 

3. moveShark() : 상어 이동

순열을 이용했습니다. 저는 순열 부분에서 틀려서 시간이 꽤 오래 잡아먹었는데,

테스트케이스 4, 5번 틀리시는 분들은 방문했던 곳을 또다시 방문할 수 있게 바꿔보세요...

하지만 방문한 곳에 대해서 물고기가 있는 곳이라면 카운트를 중복으로 안하게끔 visitCnt를 만들어줘서 판단했습니다.

또한 순열을 사용한 이유는 상좌하우 탐색을 하기 위해서입니다. 

 

4. fishSmellDelete() : 물고기냄새 있는 칸 -1

4X4 smellMap 물고기 냄새를 저장해준걸 -1 씩 해줍니다.

 

5. insertCopyFish() : 복사해둔 물고기들을 삽입해줍니다.

1 과정에서 복사해둔 물고기들을 map에 다시 넣어줍니다.

 

조건들이 너무 많기에 하나라도 놓치면 디버깅 하기 빡신거 같아요..

상어 이동 과정에서 재방문 못할거라 생각해서 풀었는데, 그거때문에 시간을 너무 많이 잡아먹었네요..

 

하지만 구현이 빡센만큼 특별한 알고리즘은 없는거 같습니다.

 

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

public class Main {
	static Queue<Integer>[][] map = new LinkedList[4][4];
	static Queue<Integer>[][] copy = new LinkedList[4][4];
	static boolean[][] visited ;
	static int[][] visitCnt;
	static int[][] smellMap = new int[4][4];
	static int[] sharkDir = new int[3];
	static int M, S, max;
	static Shark shark;
	// ←, ↖, ↑, ↗, →, ↘, ↓, ↙ 물고기 이동 
	static int[] dx = {0, -1, -1, -1, 0, 1, 1, 1};
	static int[] dy = {-1, -1, 0, 1, 1, 1,  0, -1};
	// 상좌하우 상어 
	static int[] sx = {-1, 0, 1, 0};
	static int[] sy = {0, -1, 0, 1};
	
	public static void main(String[] args) throws Exception{
		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 LinkedList<Integer>();
				copy[i][j] = new LinkedList<Integer>();
			}
		}
		
		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()) - 1;
			map[x][y].add(d);
			
		}
		st = new StringTokenizer(br.readLine());
		shark = new Shark(Integer.parseInt(st.nextToken()) - 1, Integer.parseInt(st.nextToken()) - 1);
		
		for(int i = 0 ; i < S ; i++) {
			//물고기 복사 
			copyFishmap();
			
			// 물고기 이동 
			moveFish();
			
			// 상어 이동
			moveShark();
			
			// 두번전 물고기 냄새 없애기 visited
			fishSmellDelete();
			
			//물고기 복사 떠놓은거 map 넣기 
			insertCopyFish();
		}
		max = 0;
		for(int i = 0 ; i < 4; i++) {
			for(int j = 0 ; j < 4 ; j++) {
				max += map[i][j].size();
			}
		}
		System.out.println(max);
	}
	
	private static void insertCopyFish() {
		for(int i = 0 ; i < 4;  i++) {
			for(int j = 0 ; j < 4; j++) {
				
				while(!copy[i][j].isEmpty()) {					
					map[i][j].add(copy[i][j].poll());
				}
			}
		}
	}

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

	private static void moveShark() {
		//상 좌 하 우 
		max = Integer.MIN_VALUE;
		visitCnt = new int[4][4];
		findSharkDir(0, 0, shark.x, shark.y, new int[]{-1, -1, -1});
		visited = new boolean[4][4];
		for(int i = 0 ; i < 3; i++) {
			shark.x = shark.x + sx[sharkDir[i]];
			shark.y = shark.y + sy[sharkDir[i]];
			if(map[shark.x][shark.y].size() != 0 && visited[shark.x][shark.y] == false) {
				visited[shark.x][shark.y] = true;
				
				map[shark.x][shark.y].clear();
				
				smellMap[shark.x][shark.y] = 3;
			}
		}
		
	}
	private static void findSharkDir(int depth, int count, int x, int y, int[] arr) {
		if(depth == 3) {
			if(count > max) {
				for(int i = 0 ; i < 3; i++) {
					sharkDir[i] = arr[i];
					max = count;
				}
			}
			return;
		}
		for(int dir = 0 ; dir < 4; dir++) {
			int nx = x + sx[dir];
			int ny = y + sy[dir];
			
			if(0 > nx || nx >= 4 || 0 > ny || ny >= 4) continue;
			arr[depth] = dir;
			if(visitCnt[nx][ny] == 0) {
				visitCnt[nx][ny] += 1;
				findSharkDir(depth + 1, count + map[nx][ny].size(), nx, ny, arr);
			}
			else {
				visitCnt[nx][ny] += 1;
				findSharkDir(depth + 1, count, nx, ny, arr);
			}
			visitCnt[nx][ny] -= 1;
		}
	}

	private static void moveFish() {
		int[][] sizeMap = new int[4][4];
		for(int x = 0 ; x < 4 ; x++) {
			for(int y = 0 ; y < 4; y++) {
				sizeMap[x][y] = map[x][y].size();
			}	
		}
		
		for(int x = 0 ; x < 4 ; x++) {
			for(int y = 0 ; y < 4; y++) {
				int size = sizeMap[x][y];
				if(size == 0) continue;
				
				Loop : for(int idx = 0 ; idx < size ; idx++) {
					int dir = map[x][y].poll();
					
					for(int d = 0 ; d < 8 ; d++) {
						
						if(d != 0) dir -= 1;
						if(dir == -1) dir = 7;
						int nx = x + dx[dir];
						int ny = y + dy[dir];
						
						if(0 > nx || nx >= 4 || 0 > ny || ny >= 4) continue;
						
						if(nx == shark.x && ny == shark.y) continue;
						
						if(smellMap[nx][ny] != 0) continue;
						
						map[nx][ny].add(dir);
						continue Loop;
					}
					// 다돌고 없으면 갈 수 있는곳이 없으면 제자리
					dir -= 1;
					map[x][y].add(dir);
				}
			}
		}
	}
	private static void copyFishmap() {
		for(int i = 0 ; i < 4 ; i++) {
			for(int j = 0 ; j < 4 ; j++) {
				copy[i][j].clear();
				int size = map[i][j].size();
				
				if(size > 0) {
					for(int k = 0 ; k < size ; k ++) {
						int tmp = map[i][j].poll();

						copy[i][j].add(tmp);
						map[i][j].add(tmp);
					}
				}
			}
		}
	}

	private static class Shark{
		int x, y;

		public Shark(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}