[백준] 19236 청소년 상어

문제

---

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

19236번: 청소년 상어

 

아기 상어가 성장해 청소년 상어가 되었다.

4×4크기의 공간이 있고, 크기가 1×1인 정사각형 칸으로 나누어져 있다. 공간의 각 칸은 (x, y)와 같이 표현하며, x는 행의 번호, y는 열의 번호이다. 한 칸에는 물고기가 한 마리 존재한다. 각 물고기는 번호와 방향을 가지고 있다. 번호는 1보다 크거나 같고, 16보다 작거나 같은 자연수이며, 두 물고기가 같은 번호를 갖는 경우는 없다. 방향은 8가지 방향(상하좌우, 대각선) 중 하나이다.

오늘은 청소년 상어가 이 공간에 들어가 물고기를 먹으려고 한다. 청소년 상어는 (0, 0)에 있는 물고기를 먹고, (0, 0)에 들어가게 된다. 상어의 방향은 (0, 0)에 있던 물고기의 방향과 같다. 이후 물고기가 이동한다.

물고기는 번호가 작은 물고기부터 순서대로 이동한다. 물고기는 한 칸을 이동할 수 있고, 이동할 수 있는 칸은 빈 칸과 다른 물고기가 있는 칸, 이동할 수 없는 칸은 상어가 있거나, 공간의 경계를 넘는 칸이다. 각 물고기는 방향이 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전시킨다. 만약, 이동할 수 있는 칸이 없으면 이동을 하지 않는다. 그 외의 경우에는 그 칸으로 이동을 한다. 물고기가 다른 물고기가 있는 칸으로 이동할 때는 서로의 위치를 바꾸는 방식으로 이동한다.

물고기의 이동이 모두 끝나면 상어가 이동한다. 상어는 방향에 있는 칸으로 이동할 수 있는데, 한 번에 여러 개의 칸을 이동할 수 있다. 상어가 물고기가 있는 칸으로 이동했다면, 그 칸에 있는 물고기를 먹고, 그 물고기의 방향을 가지게 된다. 이동하는 중에 지나가는 칸에 있는 물고기는 먹지 않는다. 물고기가 없는 칸으로는 이동할 수 없다. 상어가 이동할 수 있는 칸이 없으면 공간에서 벗어나 집으로 간다. 상어가 이동한 후에는 다시 물고기가 이동하며, 이후 이 과정이 계속해서 반복된다.

<그림 1>

 

<그림 1>은 청소년 상어가 공간에 들어가기 전 초기 상태이다. 상어가 공간에 들어가면 (0, 0)에 있는 7번 물고기를 먹고, 상어의 방향은 ↘이 된다. <그림 2>는 상어가 들어간 직후의 상태를 나타낸다.

<그림 2>

 

이제 물고기가 이동해야 한다. 1번 물고기의 방향은 ↗이다. ↗ 방향에는 칸이 있고, 15번 물고기가 들어있다. 물고기가 있는 칸으로 이동할 때는 그 칸에 있는 물고기와 위치를 서로 바꿔야 한다. 따라서, 1번 물고기가 이동을 마치면 <그림 3>과 같아진다.

<그림 3>

 

2번 물고기의 방향은 ←인데, 그 방향에는 상어가 있으니 이동할 수 없다. 방향을 45도 반시계 회전을 하면 ↙가 되고, 이 칸에는 3번 물고기가 있다. 물고기가 있는 칸이니 서로 위치를 바꾸고, <그림 4>와 같아지게 된다.

<그림 4>

 

3번 물고기의 방향은 ↑이고, 존재하지 않는 칸이다. 45도 반시계 회전을 한 방향 ↖도 존재하지 않으니, 다시 회전을 한다. ← 방향에는 상어가 있으니 또 회전을 해야 한다. ↙ 방향에는 2번 물고기가 있으니 서로의 위치를 교환하면 된다. 이런 식으로 모든 물고기가 이동하면 <그림 5>와 같아진다.

<그림 5>

 

물고기가 모두 이동했으니 이제 상어가 이동할 순서이다. 상어의 방향은 ↘이고, 이동할 수 있는 칸은 12번 물고기가 있는 칸, 15번 물고기가 있는 칸, 8번 물고기가 있는 칸 중에 하나이다. 만약, 8번 물고기가 있는 칸으로 이동하면, <그림 6>과 같아지게 된다.

<그림 6>

 

상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 구해보자.

 

 

풀이

---

우선 물고기가 DFS 를 이용해서 문제를 풀어야한다.

 

이 때, 문제점이 2가지 있다.

상어가 물고기를 먹으면 -> 살아있는 물고기의 리스트가 변함, map에서 상어의 위치가 변함 

 

int배열과 list는 값이 바뀌면 같이 바뀌게 되기 때문에 (call by reference 기 때문)

따라서 값을 바뀌지 않게 dfs를 시행하기 전 map 과 list 를 깊은 복사를 하여 값을 저장한다.

그런 뒤에 현재 상어의 위치에서 1번째 물고기, 2번째 물고기, 3번째 물고기를 먹었을 때 결과값을 DFS로 각각 구한다.

 

 

Call by Reference가 중요한 문제였다. 그것만 해결하면 구현 자체를 어렵지 않게 할 수 있을 것이다.

 

<전체코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	
	static int[][] move = { {-1, 0}, {-1, -1}, {0, -1}, {1, -1}, {1, 0}, {1, 1}, {0, 1}, {-1, 1}};
	static int[][] map;
	static List<node> list;
	static int answer;
	
	
	public static void main(String[] args) throws IOException {
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		list = new ArrayList<>();
		
		map = new int[4][4];
		for(int i = 0 ; i < 4 ; i++) {
			StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
			for(int j = 0 ; j < 4 ; j++) {
				int id = Integer.parseInt(st.nextToken());
				int dir = Integer.parseInt(st.nextToken()) - 1;
				
				node now = new node(i, j, dir, id, true);
				list.add(now);
				map[i][j] = now.id;				
			}
		}
		
		Collections.sort(list);
		
		node fish = list.get(map[0][0] - 1);
		Shark shark = new Shark(0, 0, fish.dir, fish.id);
		fish.alive = false;
		map[0][0] = -1;
		
		answer = 0;		
		solution(map, shark, list);		
		System.out.println(answer);
	}
	
	static void moveFish(int[][] map, List<node> list) {
		
		for(node fish : list) {
			if(fish.alive) {				
				for(int i = 0 ; i < 8 ; i++) {
					int ndir = (fish.dir + i) % 8;
					int nx = fish.x + move[ndir][0];
					int ny = fish.y + move[ndir][1];
					
					if(nx < 0 || nx >= 4 || 0 > ny || ny >= 4 || map[nx][ny] == -1 ) { continue;}
						
					
					map[fish.x][fish.y] = 0;
					
					if(map[nx][ny] == 0) {
						fish.x = nx;
						fish.y = ny;
					}
					else{
						node tmp = list.get(map[nx][ny] - 1);
						tmp.x = fish.x;
						tmp.y = fish.y;
						map[fish.x][fish.y] = tmp.id;
						
						fish.x = nx;
						fish.y = ny;
					}
					
					map[fish.x][fish.y] = fish.id;
					fish.dir = ndir;
					
					break;
				}
			}
		}
		
		return;
	}
	
	static int[][] copyMap(int[][] map){
		int[][] tmp = new int[4][4];
		for(int i = 0 ; i < 4 ; i++) {
			for(int j = 0 ; j < 4 ; j++) {
				tmp[i][j] = map[i][j];
			}
		}
		return tmp;	
	}
	
	static List<node> copyList(List<node> list){
		List<node> tmp = new ArrayList<>();
		
		list.forEach(e -> tmp.add(new node(e.x, e.y, e.dir, e.id, e.alive)));
		
		return tmp;
	}
	
	static void solution(int[][] map, Shark shark, List<node> list) {
		
		answer = Math.max(shark.sum, answer);
		
		moveFish(map, list);
		
		for(int i = 1 ; i < 4; i++) {
			int nx = shark.x + move[shark.dir][0] * i;
			int ny = shark.y + move[shark.dir][1] * i;
			
			if(nx < 0 || nx >= 4 || ny < 0 || ny >= 4 || map[nx][ny] == 0) { continue; }
			
			int[][] copy = copyMap(map);
			List<node> copyList = copyList(list);
			
			copy[shark.x][shark.y] = 0;
			node fish = copyList.get(map[nx][ny] - 1);
			Shark copyShark = new Shark(fish.x, fish.y, fish.dir, shark.sum + fish.id);
			fish.alive = false;
			copy[nx][ny] = -1;
			
			solution(copy, copyShark, copyList);			
		}
	}
	
	static class Shark{
		
		int x, y, dir, sum;
		
		Shark(int x, int y, int dir, int sum){
			this.x = x;
			this.y = y;
			this.dir = dir;
			this.sum = sum;
		}
	}
	
	static class node implements Comparable<node>{
		int x, y, dir;
		int id;
		boolean alive;
		
		public node(int x, int y, int dir, int id, boolean alive) {
			this.x = x;
			this.y = y;
			this.dir = dir;
			this.id = id;
			this.alive = alive;
		}

		@Override
		public int compareTo(node o) {
			return this.id - o.id;
		}
	}
}