BOJ - 청소년 상어 19236번 (JAVA)

❓ 문제 - 백준 청소년 상어 19236번 - JAVA 풀이법

 

출처 

(https://www.acmicpc.net/problem/19236)

 

 

📝 문제해결법

1. 이 문제는 구현+DFS(백트래킹)으로 풀었다.

• HashMap을 통해 key는 물고기의 번호, value는 물고기의 정보(위치 x,y, 방향)를 담은 객체를 관리한다.
• 2차원 배열 map으로 물고기의 위치와 함께 i, j행에 물고기의 번호를 담는다.
• s_x, s_y는 상어의 위치이며, 상어의 방향은 처음 0,0 의 물고기를 먹은 후 해당 물고의 방향을 가지게 된다.
• DFS(백트래킹)을 통해 물고기의 이동, 상어가 갈 수 있는 방향 내에서 움직임을 완전탐색 해서 먹을 수 있는 물고기의 최대갯수를 구한다.
• 물고기의 이동을 구현할 때 한번에 이동하므로 map_copy라는 2차원 배열을 활용하면서 움직임을 처리한다.
• 물고기가 45도씩 반시계방향으로 회전하면서 이동할 수 있는 칸을 탐색하고 만약 이동할 곳을 찾았는데 물고기가 이미 이동해서 들어있는 곳이라면 해당 물고기와 위치와 방향을 교환 처리해준다.
• 물고기의 이동을 다 처리한 후에 상어의 이동이 가능한지 살피기 위해 현재 상어의 방향대로 살피면서 갈 수 있는 곳이 있다면 물고기를 먹고, 물고기의 위치와 방향을 상어의 위치와 방향으로 교체한 후에 재귀를 탄다.

 

 

💻 소스코드

// BOJ - 청소년 상어(19236번)
// 백트래킹

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


public class Main_19236 {
	public static int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1};
	public static int[] dy = {0, -1, -1, -1, 0, 1, 1, 1};
	public static int ans;
	public static class Fish {
		int x;
		int y;
		int dir;
		public Fish(int x, int y, int dir) {
			this.x = x;
			this.y = y;
			this.dir = dir;
		}
	}
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		int[][] map = new int[4][4];
		HashMap<Integer, Fish> hash = new HashMap<>();
		
		for(int i=0;i<4;i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j=0;j<4;j++) {
				int num = Integer.parseInt(st.nextToken());
				int dir = Integer.parseInt(st.nextToken());
				map[i][j] = num;
				hash.put(num, new Fish(i, j, dir-1));
			}
		}
		
		int s_x = 0;
		int s_y = 0;
		Fish first = hash.get(map[0][0]);
		ans = map[0][0];
		int s_dir = first.dir;
		int num = map[0][0];
		map[0][0] = 0;
		hash.remove(num);


		dfs(map, hash, num, new Fish(s_x, s_y, s_dir));
		System.out.println(ans);
		

	}
	
	public static void dfs(int[][] map, HashMap<Integer, Fish> hash, int sum, Fish shark) {
		ans = Math.max(ans, sum);
		
		int[][] map_copy = new int[4][4];
		for(int i=0;i<4;i++) {
			map_copy[i] = map[i].clone();
		}
		HashMap<Integer, Fish> hash_copy = (HashMap<Integer, Fish>) hash.clone();
		
		// 물고기의 이동
		for(int k=1;k<=16;k++) {
			if(!hash.containsKey(k)) continue;
			Fish fish = hash_copy.get(k);
			if(map[fish.x][fish.y] == 0) continue;
			
			int dir = fish.dir;
			int turn_cnt = 0;
			boolean check = false;
			int nx = fish.x;
			int ny = fish.y;
			while(turn_cnt++ < 8) {
				nx = fish.x + dx[dir];
				ny = fish.y + dy[dir];
				if(nx < 0 || nx >= 4 || ny < 0 || ny >= 4 || (nx == shark.x && ny == shark.y)) {
					dir = (dir+1) % 8;
				} else {
					check = true;
					break;
				}
			}
			// 물고기 이동가능 
			if(check) {
				if(map_copy[nx][ny] != 0) {
					map_copy[fish.x][fish.y] = map_copy[nx][ny];
					Fish move_fish = hash_copy.get(map_copy[nx][ny]);
					hash_copy.put(map_copy[nx][ny], new Fish(fish.x, fish.y, move_fish.dir));
					map_copy[nx][ny] = k;
					hash_copy.put(k, new Fish(nx, ny, dir));
	
				} else {
					map_copy[nx][ny] = k;
					hash_copy.put(k, new Fish(nx, ny, dir));
					map_copy[fish.x][fish.y] = 0;
				}
			}

		}


		
		// 상어 이동 가능 ?
		for(int m=1;m<=4;m++) {
			int nx = shark.x + dx[shark.dir] * m;
			int ny = shark.y + dy[shark.dir] * m;
	
			if(nx < 0 || nx >= 4 || ny < 0 || ny >= 4) break;
			if(map_copy[nx][ny] != 0) {
				int num = map_copy[nx][ny];
				map_copy[nx][ny] = 0;
				int dir = hash_copy.get(num).dir;
				hash_copy.remove(num);
				dfs(map_copy, hash_copy, sum+num, new Fish(nx, ny, dir));
				hash_copy.put(num, new Fish(nx, ny, dir));
				map_copy[nx][ny] = num;
			}
			
		}
		
	}
	
	

}