[Java] 백준 알고리즘 19236번 문제 : 삼성 SW 역량 테스트 기출 문제 - 청소년 상어 (DFS, 깊이 우선 탐색)

--- 문제 ---

 

 

 

 

--- 코드 ---

 

이 문제의 특이 사항은 다음과 같습니다.

 

• dfs 의 한 스텝이 끝나고 이전 스텝으로 돌아올 때, 원래의 공간, 물고기 상태로 다시 돌아와야 하는데, 이 부분이 매우 복잡합니다.
  • 따라서 한 스텝마다 공간과 물고기의 상태를 따로 복사해서 그 복사한 정보를 dfs 마다 넘겨주는 상태로 코드를 짰습니다.
  • 메모리를 더 쓰게 되기는 하지만, 애초에 문제의 표본이 N은 4이고 (4x4 공간), dfs 의 스텝(깊이)이 많은 편이 아니기 때문에(최대 15개) 메모리 제한에 걸리지 않는다고 판단했습니다.
• 상어는 방향에 있는 칸으로 이동할 수 있는데, 한 번에 여러 개의 칸을 이동할 수 있다. 상어가 물고기가 있는 칸으로 이동했다면, 그 칸에 있는 물고기를 먹고, 그 물고기의 방향을 가지게 된다. 이동하는 중에 지나가는 칸에 있는 물고기는 먹지 않는다. 물고기가 없는 칸으로는 이동할 수 없다.
  
  • 문제의 이 말이, 상어가 다음 칸에 물고기가 없으면 그 다음칸에 있는 물고기를 도달하지 못한다는 뜻이 아니라, 한번에 2칸도 움직일 수 있어서 중간에 물고기가 있든 없든 2번째 칸으로도 이동할 수 있다는 뜻이었습니다.
  • 따라서, 상어의 방향을 따라간 바로 다음 칸이 아니라 상어의 방향으로 갈 수 있는 전체 칸 중에서 물고기가 있는지 없는지를 체크해야 했습니다. 이 체크하는 코드는 다음과 같습니다.
    
    

	// 상어가 움직일 곳이 있는지 체크하는 함수
	public static boolean check(Fish shark, int[][] cmap) {
		int nexty= shark.y+DIRECTIONS[shark.direc][0];
		int nextx= shark.x+DIRECTIONS[shark.direc][1];
		while(nexty>=0 && nexty<N && nextx<N && nextx>=0) {
			
			if(cmap[nexty][nextx]>0) return true;
			
			nexty+=DIRECTIONS[shark.direc][0];
			nextx+=DIRECTIONS[shark.direc][1];
			
			
		}
		return false;
	}

 

다음은 전체 코드 입니다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.StringTokenizer;

class Fish{
	
	int y,x,direc;
	
	public Fish(int y, int x, int direc){
		this.y = y;
		this.x = x;
		this.direc = direc;
	}

	public void move(int y, int x) {
		this.y = y;
		this.x = x;
	}
	
	public void rotate() {
		direc = (direc==7)? 0 : direc+1;
	}

	@Override
	public String toString() {
		return "Fish [y=" + y + ", x=" + x + ", direc=" + direc + "]";
	}
	
}


public class Bj19238 {
	
	public static final int[][] DIRECTIONS = {{-1,0},{-1,-1},{0,-1},{1,-1},{1,0},{1,1},{0,1},{-1,1}};
	public static int[][] map ;
	public static final int N = 4;
	public static int max;
	public static Fish[] fishes;
	public static boolean[] eated;
	
	public static int stoi(String s) {
		return Integer.parseInt(s);
	}
	public static void main(String[] args) throws IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		map = new int[N][N];
		fishes = new Fish[17];
		eated = new boolean[17];
		
		for(int i=0; i<N; ++i) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; ++j) {
				int tmp = stoi(st.nextToken());
				map[i][j] = tmp;
				int direc = stoi(st.nextToken());
				fishes[tmp] = new Fish(i,j,direc-1);
			}
		}
		max = map[0][0];
		
		// eat
		eated[map[0][0]]=true;
		int sum = map[0][0];
		map[0][0] = -1; // here
		Fish shark = new Fish(0,0,fishes[sum].direc);
		
		move(map,fishes);
		dfs(shark,sum,map,fishes);
		
		System.out.println(max);
	}
	
	// 상어가 움직일 곳이 있는지 체크하는 함수
	public static boolean check(Fish shark, int[][] cmap) {
		int nexty= shark.y+DIRECTIONS[shark.direc][0];
		int nextx= shark.x+DIRECTIONS[shark.direc][1];
		while(nexty>=0 && nexty<N && nextx<N && nextx>=0) {
			
			if(cmap[nexty][nextx]>0) return true;
			
			nexty+=DIRECTIONS[shark.direc][0];
			nextx+=DIRECTIONS[shark.direc][1];
			
			
		}
		return false;
	}
	public static void dfs(Fish shark, int sum, int[][] cmap, Fish[] cfishes) {
		// basis
		if(!check(shark,cmap)) {
			if(sum>max) {
				max = sum;
			}
			return;
		}
		
		// 이동 가능한 곳으로 다 이동
		int dir = shark.direc;
		int nexty= shark.y+DIRECTIONS[dir][0];
		int nextx= shark.x+DIRECTIONS[dir][1];
		// 벽을 만날 때까지 상어의 방향으로 이동
		while(nexty>=0 && nexty<N && nextx<N && nextx>=0 ) {
			// if shark can eat fish
			if(cmap[nexty][nextx]>0) {
				// copy
				int[][] ccmap = new int[N][N];
				for(int i=0; i<N; ++i) {
					ccmap[i] = cmap[i].clone();
				}
				Fish[] ccfishes = new Fish[17];
				for(int i=1; i<17; ++i) {
					ccfishes[i] = new Fish(cfishes[i].y, cfishes[i].x, cfishes[i].direc);
				}
				// next coordinate
				int num = ccmap[nexty][nextx];
				Fish next_shark = new Fish(nexty,nextx,ccfishes[num].direc);
				// eat
				eated[num] = true;
				ccmap[shark.y][shark.x] = 0;
				ccmap[nexty][nextx] = -1;
				// then
				move(ccmap, ccfishes);
				dfs(next_shark,sum+num,ccmap,ccfishes);
				// back
				eated[num] = false;
				
				
			}
			nexty+= DIRECTIONS[dir][0];
			nextx+= DIRECTIONS[dir][1];
		}
		
	}
	
	// 물고기들 이동 함수
	public static void move(int[][] cmap, Fish[] cfishes) {
		// 1번 부터 16번 물고기까지 이동
		for(int i=1; i<17; ++i) {
			// not eaten
			if(!eated[i]) {
				Fish current = cfishes[i];
				
				for(int j=0; j<8; ++j) {
					
					int nexty = current.y + DIRECTIONS[current.direc][0];
					int nextx = current.x + DIRECTIONS[current.direc][1];
					
					if(nexty>=0 && nexty<N && nextx>=0 && nextx<N && cmap[nexty][nextx]>-1) {
						
						int tmp = 0;
						if(cmap[nexty][nextx]!=0) {
							tmp = cmap[nexty][nextx];
							cfishes[tmp].move(current.y, current.x);
						}
						
						cmap[nexty][nextx] = i;
						cmap[current.y][current.x] = tmp;
						
						current.move(nexty,nextx);
						
						break;
					}
					
					current.rotate();
					
				}
				
			}
			
		}
		
	}

}

 

 

--- 출처 ----

 

www.acmicpc.net/problem/19236

19236번: 청소년 상어