[BaekJoon] 백준 19236번 _ 청소년 상어 for JAVA

 

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

19236번: 청소년 상어

 

 

문제

 

---

 

진짜 별거 아닌데 요즘 코로롱 때문에 알고리즘 며칠 쉬었더니 뇌가 굳어버려서 엄청 오래걸렸다.

 

핑계인가... 아무튼

 

 

특별할 것 없는 구현 + 백트래킹을 가미한 문제이다.

 

 

상어가 잡아먹을 수 있는 물고기가 여러마리이기 때문에 dfs로 모든 경우의 수를 확인해야 한다.

 

 

처음에 그냥 그리디하게 큰거 잡아먹다가... 아닌걸 깨닫고 백트래킹으로 바꾸는데

 

 

이게 물고기 움직임 -> 상어 움직임 -> 물고기 움직임 -> 상어 못움직여서 끝남

 

순서라서 물고기 움직이기 전 -> 상어 움직이기 전 으로 백해야하거덩요

 

 

그래서 갑자기 머리가 복잡해지면서... 띠용때용 난리가 났었다. 바본가..

 

배열은 깊은 복사이기 때문에 넘겨줄 때 매개변수로 넘겨도 그걸 참조하는 모든 배열이 바뀐다.

 

 

그래서 물고기를 움직일 때 그 map이 싹다 바뀌니까

 

dfs를 들어가서 그 'map'이 아니라 map을 clone한 애를 사용해야 백트래킹을 할 수 있다.

 

 

 

순서

1. 물고기 움직이기

   - 이동O : 이동할 수 있는 방향 찾기 - 반시계로 훑음. 이동할 수 없을 수도 있음

       - 빈칸

       - 다른 물고기 (자리 바꿈)

   - 이동X

       - 상어

       - 공간 경계 밖

 

2. 상어 움직이기

   - 그 방향에 있는 여러칸 중 하나로 가능

       - 모든 경우의 수를 훑어야함 : dfs + 백트래킹 사용

   - 이동 -> 물고기 먹음 -> 그 방향 가짐

   - 어느 칸에도 물고기 x or 경계 밖 -> 끝

 

 

코드

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

public class Main {
	
	static class Seat{
		int x,y,dir;

		public Seat(int x, int y, int dir) {
			super();
			this.x = x;
			this.y = y;
			this.dir = dir;
		}

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

	static HashMap<Integer, Seat> fish;
	static Seat shark;
	static int map[][];
	static int dx[] = {0,-1,-1,0,1,1,1,0,-1};
	static int dy[] = {0,0,-1,-1,-1,0,1,1,1};
	static int answer = Integer.MIN_VALUE;
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		map = new int[4][4]; // 물고기 번호를 저장할 배열
		fish = new HashMap<>(); // 물고기 번호 : 자리와 방향
		int startNum = 0;
		
		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());
				
				if(i == 0 && j == 0) {
					shark = new Seat(i, j, dir);
					startNum = num;
					map[i][j] = 0;
					continue;
				}
				map[i][j] = num;
				fish.put(num, new Seat(i, j, dir));
			}
		}
		Move(startNum, map, fish, shark);
		System.out.println(answer);
	}
	private static void Move(int total, int[][] map, HashMap<Integer, Seat> fish, Seat shark) {
		answer = Math.max(answer, total);
		// 맵과 물고기 hashmap은 깊은 복사 후 그것을 사용함 (백트래킹 하기 위해)
		int map_copy[][] = new int[4][4];
		for(int i=0; i<4; i++)
			map_copy[i] = map[i].clone();
		
		
		HashMap<Integer, Seat> fish_copy = (HashMap<Integer, Seat>) fish.clone();
		
        // 물고기 번호가 작은 순서대로 이동
		ArrayList<Integer> keySet = new ArrayList<>(fish_copy.keySet());
		Collections.sort(keySet);
		
		for(int key : keySet) {
			Seat fishSeat = fish_copy.get(key);
			int x = fishSeat.x;
			int y = fishSeat.y;
			int dir = fishSeat.dir;
			
			// 1-2. 물고기 이동하자.
			for(int d=dir; d<dir+9; d++) {
				int di = d%9;
				if(di == 0) continue;
				int nx = x + dx[di]; // 이동하려는 칸 x
				int ny = y + dy[di]; // 이동하려는 칸 y
				// 이동하려는 칸에 상어가 없고 공간 경계 안쪽이라면
				if(nx >= 0 && nx < 4 && ny >= 0 && ny < 4 && !(nx == shark.x && ny == shark.y)) {
					// 이동하려는 칸에 아무것도 없다면 그냥 이동시킨다.
					if(map_copy[nx][ny] == 0) {
						map_copy[nx][ny] = key;
						map_copy[x][y] = 0;
						fish_copy.put(key, new Seat(nx, ny, di));
					} 
					// 이동하려는 칸에 물고기가 있다면 자리를 바꾼다.
					else {
						swipe(key, di, map_copy[nx][ny], map_copy, fish_copy); // 양쪽 자리의 key값(number)을 보냄
					}
					break;
				} else {
					continue;
				}
			}

		}
		
		// 상어의 x,y,dir
		int x = shark.x;
		int y = shark.y;
		int dir = shark.dir;

		while(true) {
			x += dx[dir];
			y += dy[dir];
			
			if(x < 0 || x >= 4 || y < 0 || y >= 4) break;
			if(map_copy[x][y] == 0) continue;
			int fishNum = map_copy[x][y];
			int fishDir = fish_copy.get(fishNum).dir;
			
			// 먹으러가기
			map_copy[x][y] = 0; // 상어 위치는 map에 표시 안하고 shark.x, shark.y 사용
			fish_copy.remove(fishNum); // 물고기 먹었어
			
			Move(total + fishNum, map_copy, fish_copy, new Seat(x,y,fishDir));				
			
			// 백트래킹으로 되돌리기
			map_copy[x][y] = fishNum;
			fish_copy.put(fishNum, new Seat(x, y, fishDir));

			
		}
		answer = Math.max(answer, total);
	}
	private static void swipe(int key1, int d, int key2, int[][] map_copy, HashMap<Integer, Seat> fish_copy) {
		Seat seat1 = fish_copy.get(key1);
		Seat seat2 = fish_copy.get(key2);
		
		int x1 = seat1.x;
		int y1 = seat1.y;
		int dir1 = d;
		
		int x2 = seat2.x;
		int y2 = seat2.y;
		int dir2 = seat2.dir;
		
		// 바꿀 것: map자리, fish에서의 자리
		map_copy[x1][y1] = key2;
		map_copy[x2][y2] = key1;
		
		fish_copy.put(key1, new Seat(x2, y2, dir1));
		fish_copy.put(key2, new Seat(x1, y1, dir2));
		
	}

}

 

 

 

성능

 

 

 

 

백트래킹 문제 조지기 들어가야겠다. 화이팅