[백준] 23290 마법사 상어와 복제 - 구현(Implementation) + 시뮬레이션(Simulation) + 깊이우선탐색을 활용한 중복순열(Repeated Permutation With DFS, PErmutation With Repetition And DFS) JAVA

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

23290번: 마법사 상어와 복제

코드설명

구현(Implementation) + 시뮬레이션(Simulation) 문제입니다.

 

전체적인 코드 로직입니다.

1. 물고기의 이동: 모든 물고기가 한 칸씩 이동하면서 격자의 범위를 벗어나거나 상어가 있는 칸으로는 이동하지 않도록 조건을 체크합니다. 물고기는 자신이 가지고 있는 이동 방향이 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전시킵니다.
2. 상어의 이동과 먹이 찾기: 상어는 연속해서 3칸을 이동합니다. 가능한 이동 방법 중에서 제외되는 물고기의 수가 가장 많은 방법을 선택하여 최대로 먹을 수 있는 물고기 수를 찾습니다. 그 후, 해당 방법으로 상어를 이동시켜 실제로 물고기를 먹습니다.
3. 물고기의 냄새 갱신: 물고기가 사라진 위치에 냄새를 남기고, 3번 과정 직후에 격자에서 사라지도록 냄새를 갱신합니다.
4. 복제된 물고기 복원: 1번에서 사용한 복제마법이 완료되면, 복제된 물고기를 실제 위치에 복원합니다.
5. 반복: 주어진 시간(S)만큼 1~4의 과정을 반복하며 최종적으로 먹을 수 있는 물고기 수를 계산합니다.

문제에서 실제 구현시 제가 겪었던 오류사항 혹은 주의해야할점들입니다.

1. 문제 조건 중 아래의 조건입니다. (문제에서는 2번조건)

1. 모든 물고기가 한 칸 이동한다. 상어가 있는 칸, 물고기의 냄새가 있는 칸, 격자의 범위를 벗어나는 칸으로는 이동할 수 없다. 각 물고기는 자신이 가지고 있는 이동 방향이 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전시킨다. 만약, 이동할 수 있는 칸이 없으면 이동을 하지 않는다. 그 외의 경우에는 그 칸으로 이동을 한다. 물고기의 냄새는 아래 3에서 설명한다.

이때, 이동할 수 있는 칸이 없으면 이동을 하지 않는다는 부분에서  originDir을 사용하여 원래 방향으로 돌려주든, 혹은

while(!fishMap[i][j].isEmpty()) {
    boolean fishMoveFlag = false;
    Fish temp = fishMap[i][j].poll();
    int originDir = temp.dir;
    for(int dir = 0; dir < 8; dir++) {
        if(dir > 0) //처음 방향부터 먼저 검사합니다.
            temp.dir = changeDirByAntiClock(temp.dir);
        int nr = temp.r + dx[temp.dir];
        int nc = temp.c + dy[temp.dir];
        if(nr < 0 || nr >= 4 || nc < 0 || nc >= 4) continue; //격자의 범위를 벗어나는경우
        if( nr == shark.r && nc == shark.c) continue; //상어가 존재하는 위치일경우
        if( fishSmellVisited[nr][nc] > 0 ) continue; //물고기의 냄새가 남아있을경우
 
        //한번 이동성공한다면 해당 물고기의 이동은 중단시킨다. 
        storeFishMap[nr][nc].offer(new Fish(nr, nc, temp.dir));
        fishMoveFlag = true;
        break;
    }
    if(fishMoveFlag == false) { //만약 이동할 수 없다면 이동을 하지 않는데, 그래도 위치에는 있어야한다.
        storeFishMap[temp.r][temp.c].add(new Fish(temp.r, temp.c, originDir)); //이 부분에서 틀렸다.. 원래 방향으로유지해야햇다.
    }
 
}

 

아래와 같이 dir을 한번 더 반시계방향으로 45도 돌려서 원래 방향으로 돌립니다.

if(fishMoveFlag == false) { //만약 이동할 수 없다면 이동을 하지 않는데, 그래도 위치에는 있어야한다.
    temp.dir = changeDirByAntiClock(temp.dir);
    storeFishMap[temp.r][temp.c].add(new Fish(temp.r, temp.c, temp.dir)); //이 부분에서 틀렸다.. 원래 방향으로유지해야햇다.
}

 

구현할시에 현재 방향을 유지하면서 이동하지 않는경우도 넣었어야했는데

temp.dir을 8번 회전시킨다는 생각에 당연히 원래 방향으로 돌아간다고 생각하였지만, 첫 경우에는 원래 방향으로 돌기에 결국은 7번회전하므로 마지막에 한번 더 돌려주는 작업이 필요합니다.

혹은 int nDir 을 활용해서 회전과 temp.dir을 분리하거나,

originDir을 활용해서 원래 방향을 유지할 수도 있습니다.

" temp. dir "이 원래 방향으로 돌아가지 않아 올바른 값을 찾지 못했습니다.

 

이런 구현시에는 반드시 조건을 하나씩 완성시켜야합니다.

 

두번쨰는, 상어는 원래 지났던 방향도 다시 갈 수 있다는 점이고, 상어가 물고기를 먹으면 물고기를 먹었다는 처리가 필요하다는 점입니다.

 

저는 fishSize를 활용해서 존재하는 물고기의 개수를 저장하고, 먹는다면 해당 칸의 물고기를 먹음 처리를 안했었습니다.

먹음 처리해줍니다.

int[][] fishSize = new int[4][4];
for(int i=0;i<4;i++) {
    for(int j=0;j<4;j++) {
        fishSize[i][j] = fishMap[i][j].size();
    }
}
 
//만약 물고기를 만난다면 다 먹는다.
//    			for(Fish tempFish : fishMap[nsr][nsc]) {
//    				sharkEatFish += 1;
//    			}
sharkEatFish += fishSize[nsr][nsc];
fishSize[nsr][nsc] = 0;

 

또한 사전순으로 만들기 위해 방향대로 순열을 진행했고, maxSharkEat보다 커야만 해당 값이 갱신되도록 하여 사전순으로 되도록 처리했습니다.

 

자세한 설명은 모두 주석에 달아보았습니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
	public static int M, S;
	public static int answer = 0;
	public static int[] dx = {0, -1, -1, -1, 0, 1, 1, 1};
	public static int[] dy = {-1, -1, 0, 1, 1, 1, 0, -1};
	public static Shark shark;
	public static int[][] fishSmellVisited = new int[4][4];
	public static Queue<Fish>[][] fishMap = new Queue[4][4];
	public static int[] sharkMove = new int[3];
	public static int[] maxSharkEatMove = new int[3];
	public static int maxSharkEat = 0;
	public static int OUTOFBOUND = -1;
	public static int SHARKMININITIAL = -1;
	
	//상어의 이동방법을 사전 순으로 가장 앞서는 방법을 찾기 위해 다른 방향을 따로 도입한다.. 상 좌 하 우 순서이다. (반시계방향)
	public static int[] sharkDx = {-1, 0, 1, 0};
	public static int[] sharkDy = {0, -1, 0, 1};
	
    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++) {
    			fishMap[i][j] = new LinkedList<Fish>();
    		}
    	}
    	
    	for(int i=0;i<M;i++) {
    		st = new StringTokenizer(br.readLine());
    		int fx = Integer.parseInt(st.nextToken());
    		int fy = Integer.parseInt(st.nextToken());
    		int d = Integer.parseInt(st.nextToken());
    		fishMap[fx - 1][fy - 1].add(new Fish(fx - 1, fy - 1, d - 1));
		}
    	
    	st = new StringTokenizer(br.readLine());
    	int sx = Integer.parseInt(st.nextToken());
    	int sy = Integer.parseInt(st.nextToken());
    	shark = new Shark(sx - 1, sy - 1);
    	
    	
    	while(--S >= 0){
    		
    		//1. 상어가 모든 물고기에게 복제마법을 시전한다. 복제 마법은 시간이 조금 걸리기 때문에, 아래 5번에서 물고기가 복제되어 칸에 나타난다.
    		//Queue에 물고기들의 정보를 "복제"해서 넣어놓습니다.
    		Queue<Fish> copyFishQueue = new LinkedList<Fish>();
    		for(int i=0;i<4;i++) {
    			for(int j=0;j<4;j++) {
    				for(Fish temp : fishMap[i][j]) {
    					copyFishQueue.add(new Fish(temp.r, temp.c, temp.dir));	
    				}
    			}
    		}
    		
    		//2. 모든 물고기가 한칸 이동한다. 상어가 있는 칸, 물고기의 냄새가 있는 칸, 격자의 범위를 벗어나는 칸으로는 이동할 수 없다.
    		//각 물고기는 자신이 가지고 있는 이동 방향이 이동할 수 있는 칸을 향할때까지 방향을 45도 반시계 회전 시킨다.
    		//만약, 이동할 수 있는 칸이 없으면 이동을 하지 않는다.
    		//그외의 경우에는 그 칸으로 이동을 한다. 물고기의 냄새는 아래 3에서 설명한다.
    		Queue<Fish>[][] storeFishMap = new LinkedList[4][4];
    		for(int i=0;i<4;i++) {
    			for(int j=0;j<4;j++) {
    				storeFishMap[i][j] = new LinkedList<Fish>();
    			}
    		}
    		
//    		System.out.println("===========fishMap==============");
//    		for(int i=0;i<4;i++) {
//    			for(int j=0;j<4;j++) {
//    				for(Fish temp : fishMap[i][j]) {
//    					System.out.print(" "+temp.r+" "+temp.c+" "+temp.dir);
//    				}
//    			}
//    			System.out.println();
//    		}
    		
    		for(int i=0;i<4; i++) {
    			for(int j=0;j<4;j++) {
    				
    				while(!fishMap[i][j].isEmpty()) {
    					boolean fishMoveFlag = false;
    					Fish temp = fishMap[i][j].poll();
    					int originDir = temp.dir;
    					for(int dir = 0; dir < 8; dir++) {
    						if(dir > 0) //처음 방향부터 먼저 검사합니다.
    							temp.dir = changeDirByAntiClock(temp.dir);
    						int nr = temp.r + dx[temp.dir];
    						int nc = temp.c + dy[temp.dir];
    						if(nr < 0 || nr >= 4 || nc < 0 || nc >= 4) continue; //격자의 범위를 벗어나는경우
    						if( nr == shark.r && nc == shark.c) continue; //상어가 존재하는 위치일경우
    						if( fishSmellVisited[nr][nc] > 0 ) continue; //물고기의 냄새가 남아있을경우
    						
    						//한번 이동성공한다면 해당 물고기의 이동은 중단시킨다. 
    						storeFishMap[nr][nc].offer(new Fish(nr, nc, temp.dir));
    						fishMoveFlag = true;
    						break;
    					}
    					if(fishMoveFlag == false) { //만약 이동할 수 없다면 이동을 하지 않는데, 그래도 위치에는 있어야한다.
    						storeFishMap[temp.r][temp.c].add(new Fish(temp.r, temp.c, originDir)); //이 부분에서 틀렸다.. 원래 방향으로유지해야햇다.
    					}
    					
    				}
    			}
    		}
    		//얕은복사로 메모리 복사해온다.
    		fishMap = storeFishMap; 
//    		System.out.println("===========After fishMoved ==============");
//    		for(int i=0;i<4;i++) {
//    			for(int j=0;j<4;j++) {
//    				for(Fish temp : fishMap[i][j]) {
//    					System.out.print(" "+temp.r+" "+temp.c+" "+temp.dir);
//    				}
//    			}
//    			System.out.println();
//    		}
    		
    		//3. 상어가 연속해서 3칸 이동한다. 상어는 현재 칸에서 상하좌우로 인전합 칸으로 이동할 수 있다. 연속해서 이동하는 칸중에 격자의 범위를 벗어나는 칸이 있으면, 그 방법은 불가능한 이동방법이다.
    		//연속해서 이동하는 중에 상어가 물고기가 있는 같은 칸으로 이동하게 된다면, 그 칸에 있는 모든 물고기는 격자에서 제외되며, 제외되는 모든 물고기는 물고기 냄새를 남긴다.
    		// 가능한 이동 방법 중에서 제외되는 물고기의 수가 가장 많은 방법으로 이동하며, 그러한 방법이 여러가지인 경우 사전 순으로 가장 앞서는 방법을 이용한다.
    		//사전 순에 대한 문제의 하단 노트에 있다.
    		//모든 과정을 거쳐서 최대값을 구햇다면 실제로 상어가 먹히도록 처리한다.
    		//작업진행하며 바로바로 할 수도 있겠지만, 현재 자료구조형이 이러하기에 먼저 구하고 작업하도록 한다.
    		maxSharkEat = SHARKMININITIAL; //-1로 초기화한다.
    		maxSharkEatMove = new int[3];
    		sharkMovePermutation(0);
    		
    		//
    		if(maxSharkEat >= 0)
    			sharkEatFish();
    		
    		//두번 전 연습에서 생긴 물고기의 냄새가 격자에서 사라진다.
    		//이 로직은 3번 과정 직후에 격자에서 사라지기에 초기값은 3으로 처리했습니다.
//    		System.out.println("==========fishSmell================");
    		for(int i=0;i<4;i++) {
    			for(int j=0;j<4;j++) {
//    				System.out.print(" "+fishSmellVisited[i][j]);
    				if(fishSmellVisited[i][j] > 0)
    					fishSmellVisited[i][j] -= 1;
    			}
//    			System.out.println();
    		}
    		
    		//1에서 사용한 복제마법이 완료된다. 모든 복제된 물고기는 1에서의 위치와 방향을 그대로 갖게된다.
    		while(!copyFishQueue.isEmpty()) {
    			Fish temp = copyFishQueue.poll();
    			fishMap[temp.r][temp.c].add(new Fish(temp.r, temp.c, temp.dir));
    		}
    		
    	}
    	
    	for(int i=0;i<4;i++) {
    		for(int j=0;j<4; j++) {
    			answer += fishMap[i][j].size();
    		}
    	}
    	
    	System.out.println(answer);
    }
 
	//반시게방향이다.. 처음에 주어진 순서가 시계방향인줄 착각하고... 하..
    public static int changeDirByAntiClock(int dir) {
    	return ( dir - 1 ) >= 0 ? dir - 1 : 7; 
    }
    
    public static void sharkMovePermutation(int level) {
    	if(level == 3) {
    		int[][] fishSize = new int[4][4];
    		for(int i=0;i<4;i++) {
    			for(int j=0;j<4;j++) {
    				fishSize[i][j] = fishMap[i][j].size();
    			}
    		}
    		
//    		System.out.println("==============");
//    		for(int i=0;i<3;i++) {
//    			System.out.print(" "+sharkMove[i]);
//    		}
//    		System.out.println("");
    		
    		//가장 많이 갈 수 있는 방법을 구한다.
    		//연속해서 이동 중 격자의 범위를 벗어난다면, 그 방법은 불가능한 방법이다.
    		int sharkEatFish = 0;
    		int nsr = shark.r; 
    		int nsc = shark.c;
    		for(int i=0; i<3;i++) {
    			nsr = nsr + sharkDx[sharkMove[i]];
    			nsc = nsc + sharkDy[sharkMove[i]];
    			
    			//만약 격자범위를 벗어난다면, 이동못한다. 
    			if(nsr < 0 || nsr >= 4 || nsc < 0 || nsc >= 4) {
    				sharkEatFish = OUTOFBOUND;
    				return ;
    			}
    			
    			//만약 물고기를 만난다면 다 먹는다.
//    			for(Fish tempFish : fishMap[nsr][nsc]) {
//    				sharkEatFish += 1;
//    			}
    			sharkEatFish += fishSize[nsr][nsc];
    			fishSize[nsr][nsc] = 0;
    			
    		}
    		
    		//만약 최대상어가먹는양보다 더 많이 먹는다면, 해당 방법으로 갱신해준다. 
    		if(maxSharkEat < sharkEatFish) {
    			maxSharkEat = sharkEatFish;
//    			System.out.println("maxsharkEat:"+maxSharkEat);
    			for(int i=0; i<3; i++) {
    				maxSharkEatMove[i] = sharkMove[i];	
    			}
    		}
    		
    		return ;
    	}
    	
    	for(int dir = 0; dir < 4; dir++) {
    		sharkMove[level] = dir;
    		sharkMovePermutation(level + 1);
    	}
    	
    }
    
    public static void sharkEatFish() {
//    	System.out.println("========sharkEatFish==============");
    	for(int dir = 0; dir < 3; dir++) {
//    		System.out.print(" "+maxSharkEatMove[dir]);
    		shark.r = shark.r + sharkDx[maxSharkEatMove[dir]];
    		shark.c = shark.c + sharkDy[maxSharkEatMove[dir]];
    		
    		if(fishMap[shark.r][shark.c].size() > 0)
    			fishSmellVisited[shark.r][shark.c] = 3;
    		
    		while(!fishMap[shark.r][shark.c].isEmpty()) {
    			fishMap[shark.r][shark.c].poll();
    		}
    	}
    }
}
 
 
 
class Fish{
	int r;
	int c;
	int dir;
	public Fish(int r, int c, int dir) {
		this.r = r;
		this.c = c;
		this.dir = dir;
	}
}
 
class Shark{
	int r;
	int c;
	int dir;
	public Shark(int r, int c) {
		this.r = r;
		this.c = c;
	}
	public Shark(int r, int c, int dir) {
		this.r = r;
		this.c = c;
		this.dir = dir;
	}
}