[백준] BOJ 19236 청소년 상어 (골드 1)

문제

---

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

19236: 청소년 상어

---

해설

---

1. int의 3차원 배열을 통한 맵복사와 값이 작은 물고기부터 이동하기 위해 사용할 TreeMap을 선언
   1. TreeMap은 Red-Black Tree로 구현되어 있어 정렬된 상태이므로 이를 이용한다.
   2. PQ를 사용하려 했지만 만약 물고기를 이동할 때 위치를 바꿔주어야 하면 (2와 15라면) 바로 접근할 수 없다.
   3. PQ에서 15가 pop되려면 최대 3~14를 모두 빼고 난 후 15를 pop하여 값을 변경해줄 수 있기 때문
   4. 따라서 TreeMap을 통해 정렬의 장점을 사용하고 Map의 특성을 통해 키를 통해 객체에 접근할 수 있음
2. 0, 0에서 상어가 시작하므로 0, 0의 인덱스 번호를 Map 자료구조에서 삭제하고 int 맵 정보 배열에서 -1로 없음 처리
3. 위에서 0,0으로 상어가 움직였으므로 이제 물고기를 움직이도록 한다.
   1. 조건에서 물고기가 움직이지 못하면 가만히 있는다고 했지만 실제로는 움직일 수 없는 경우는 없다.
   2. 가장 왼쪽 위(0, 0)에 물고기가 있다면? → 갈 수 있는 모든 경로는 8가지이지만
      불가능한 경우는 가장자리 3가지 (왼, 왼위, 위) 나머지 5가지 중 상어는 1자리만 가능 따라서 무조건 가능하다!
4. 물고기를 이동했으니 이제 다시 상어를 이동시킨다. (백트래킹)
   1. 현재 상어가 이동할 수 있는 방향을 가장자리가 되기 전까지 모두 DFS로 보내본다.
   2. 이때, 물고기가 없는 자리는 스킵하며 (continue)
   3. 가장자리에 도착했다면 더 이상 갈 수 없으므로 탐색을 종료한다. (break, return)
   4. 더 이상 갈 수 없다면 해당 탐색의 끝이므로 현재까지 먹은 물고기의 총합을 최대로 갱신한다.

---

코드 (구현 + 시뮬레이션 + 백트래킹)

---

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

public class Main {
    static int[][][] map;

    static int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1};
    static int[] dy = {0, -1, -1, -1, 0, 1, 1, 1};

    //물고기가 살아있는지 확인하기 위한 map + 살아있다면 물고기 정보를 사용하며, 이동 시 이를 변경함
    static Map<Integer, Fish> fishMap;
    static int max = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        map = new int[4][4][2];
        //키를 작은 것부터 꺼내기 위해 TreeMap 구현체 사용
        fishMap = new TreeMap<Integer, Fish>();

        //맵 복사 대신 fish
        for (int i = 0; i < 4; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 4; j++) {
                map[i][j][0] = Integer.parseInt(st.nextToken());
                map[i][j][1] = Integer.parseInt(st.nextToken()) - 1;
                fishMap.put(map[i][j][0], new Fish(i, j, map[i][j][1]));
            }
        }

        //0, 0물고기 없애기
        fishMap.remove(map[0][0][0]);
        //x, y, dir, cost
        int[] shark = new int[]{0, 0, map[0][0][1], map[0][0][0]};
        map[0][0][0] = -1;
        simulation(shark, map, fishMap, 0);
        System.out.println(max);
    }

    private static void simulation(int[] shark, int[][][] map, Map<Integer, Fish> fishMap, int depth) {
        fishMove(map, fishMap, shark);

        int mul = 1;
        while (true) {
            int nx = shark[0] + (dx[shark[2]] * mul);
            int ny = shark[1] + (dy[shark[2]] * mul);

            //경계를 나가거나 물고기가 없으면 못간다.
            if (nx < 0 || ny < 0 || nx >= 4 || ny >= 4) {
                max = Math.max(max, shark[3]);
                break;
            }
            mul++;
            if (map[nx][ny][0] == -1) {
                continue;
            }
            Map<Integer, Fish> copyMap = copyFishMap(fishMap);
            int[][][] copy = copyMap(map);
            int cost = shark[3] + copy[nx][ny][0];
            //물고기 잡아먹기
            copyMap.remove(copy[nx][ny][0]);
            copy[nx][ny][0] = -1;

            simulation(new int[]{nx, ny, copy[nx][ny][1], cost}, copy, copyMap ,depth+1);
        }
    }

    private static void fishMove(int[][][] map, Map<Integer, Fish> fishMap, int[] shark) {
        //트리 맵 구현체 이므로 RBTree -> 작은 것부터 (기본 오름차순)
        for (Integer key : fishMap.keySet()) {
            Fish fish = fishMap.get(key);

            while (true){
                int nx = fish.x + dx[fish.dir];
                int ny = fish.y + dy[fish.dir];
                if(nx < 0 || ny < 0 || nx >= 4 || ny >= 4 || (nx == shark[0] && ny ==shark[1])) {
                    //반시계 -> 인덱스 ++
                    fish.dir = (++fish.dir) % 8; //모듈러로 인덱싱 범위내로 넣기
                    continue;
                }
                int[] temp = new int[]{map[nx][ny][0], map[nx][ny][1]};
                //이동 위치에 물고기 존재 하면
                Fish target = fishMap.get(temp[0]);
                if (target != null) {
                    target.x = fish.x;
                    target.y = fish.y;
                }
                map[nx][ny][0] = map[fish.x][fish.y][0];
                map[nx][ny][1] = fish.dir;
                map[fish.x][fish.y][0] = temp[0];
                map[fish.x][fish.y][1] = temp[1];
                fish.x = nx;
                fish.y = ny;
                break;
            }
        }
    }

    private static Map<Integer, Fish> copyFishMap(Map<Integer, Fish> fishMap) {
        Map<Integer, Fish> copy = new TreeMap<>();
        for (Integer key : fishMap.keySet()) {
            //
            Fish fish = fishMap.get(key);
            Fish copyFish = new Fish(fish.x, fish.y, fish.dir);
            copy.put(key, copyFish);
//            아래처럼 하면 객체의 참조값 복사라서 얕은 복사 -> 문제 생긴다. (주의)
//            copy.put(key, fish);
        }

        return copy;
    }

    public static int[][][] copyMap(int[][][] map){
        int[][][] copy = new int[4][4][2];
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                for (int k = 0; k < 2; k++) {
                    copy[i][j][k] = map[i][j][k];
                }
            }
        }
        return copy;
    }
}

class Fish {

    int x, y, dir;
    public Fish(int x, int t, int dir) {
        this.x = x;
        this.y = t;
        this.dir = dir;
    }
}

---

결론

---

해당 문제는 아이디어를 떠올리고 코드로 구현하는 시간보다 디버깅에 걸린 시간이 훨씬 길었다.

디버깅이 필요했던 부분은 찾고나면 허무하지만 충분히 실수 할 수 있는 부분이었다!.

바로 TreeMap에서 객체를 꺼내서 복사하는 과정에서 깊은 복사를 해야하는데 얕은 복사를 했다!.

TreeMap의 상태를 복사해서 사용하고자 copyFishMap메서드를 만들었지만
TreeMap객체는 새롭게 만들었지만 그 안에 담긴 Fish 객체는 참조 주소를 그대로 가져왔기 때문에 생긴 문제다!.
따라서 위에서 각각의 탐색(선택)에 따라 다른 결과를 가져야 할 TreeMap내부의 value 객체가 함께 사용되어
다른 선택의 경우에도 영향을 미치게 되었기 때문에 근본적으로 copy하여 사용하는 방식이 의미가 없었던 것이다!

참조 주소를 이용하여 TreeMap 내부의 value를 변경해려고 고안한 방식이

오히려 디버깅을 해야하는 요소로 작용할줄은 몰랐다 ㅠㅠ

그래도 이번에 실수했고 문제가 정확히 어떤 것인지 알았으니 다음부터 실수하지 않으면 될 것 같다!

---