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

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

 

문제

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

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

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

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

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

...

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

입력

첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 8보다 작거나 같은 자연수를 의미하고, 1부터 순서대로 ↑, ↖, ←, ↙, ↓, ↘, →, ↗ 를 의미한다.

출력

상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 출력한다.

---

방향을 지정하는 방법

• 방향의 경우, direction 을 x 와 y 로 각각 나누어서 저장하자.

static int[][] directions = { //  ↑, ↖, ←, ↙, ↓, ↘, →, ↗
        {-1, -1, 0, 1, 1, 1, 0, -1},
        {0, -1, -1, -1, 0, 1, 1, 1},
};

static String[] directions_string =
        {"↑", "↖", "←", "↙", "↓", "↘", "→", "↗"};

 

참고로, directions_string 배열은 내가 코딩하면서 직관적으로 논리를 펼칠 수 있게끔 출력하려고 만든거다. (문제에서 필요없다)

 

이런식으로 방향을 지정해놓으면, 다음과 같이 위치 변경을 이뤄낼 수 있다.

// 기존 Position 인 fishPos
// 이동한 Position 인 chgPos

// 기존 Position 인 fishPos 을 이용하여 특정 direction 으로 이동해보자.

int x = fishPos.x + directions[0][fish.dir];
int y = fishPos.y + directions[1][fish.dir];

Position chgPos = new Position(x, y);

 

---

물고기의 입력을 어떻게 저장할까?

먼저, 어떤 상태가 필요할까?

• 본인의 number
• 방향

그 다음으로 어떤 동작이 필요할까?

• 방향의 전환(반시계 방향으로 45도 회전)
• (추후 추가) 객체 간 깊은 복사를 위해서 static clone 메서드를 추가하였다.

물고기의 이동과 관련된 현재 위치는 어떻게 계산하지? (순차대로 이동해야 하므로)

• 1번 물고기부터 차례대로 어느 위치에 있는지 기록하는 순차 List<Fish> FishPos 가 필요하겠다.
• `순차대로` 에 꽂혀서 List 라고 생각했는데, 다시 잘.. 생각해보니, Map<Integer, Position> fishPosMap 으로 저장해서, 특정 Fish 의 특정 num 으로 식별하고, 해당 num 의 Fish 의 Position 값을 가져오는게 나을 것 같아, 변경하였다.

물고기가 잡아먹히면 현재 위치도 사라지고, 존재하지 않는다는 것을 표현해야 한다.

• 현재 위치를 나타내는 리스트에 위치값을 -1로 변경한다던지의 방법도 있지만, 좀더 직관적이게 boolean list 인 isEaten 를 가져가도록 하자.
• 라고 생각했는데.. 이것도 필요없어졌다. Map 으로 물고기의 존재 여부를 가져가게 되면, Map<Integer, Position> fishPosMap 에 없는 물고기는 먹혀 없는 물고기로 판별하면 된다.

// 물고기 객체
class Fish {
    int num;
    int dir;

    public Fish(int num, int dir) {
        this.num = num;
        this.dir = dir;
    }

    public static Fish clone(Fish fish) {
        return new Fish(fish.num, fish.dir);
    }

    public void rotate() {
        this.dir = (this.dir + 1) % 8;
    }

    @Override
    public String toString() {
        return String.format("%02d", num) +"(" + dir +") ";
    }
}

 

---

이제, 물고기 한마리가 이동하려고 한다고 해보자. 

물고기를 회전하려면.. 어떤 상태 정보들이 바뀔까?

• Fish[][] map : 어떤 공간에 어떤 물고기가 있는지 판별하기 위한, 어항 맵
• Map<Integer, Position> fishPosMap : 특정 number 의 물고기가 어느 Position 에 있는지 판별하는 Map 이자, 특정 물고기가 잡아먹히면 이 Map 에서 사라진다.
• Fish fish : 현재 이동하려고 하는 물고기. 현재 물고기의 num(번호) 및 dir(방향) 정보가 담겨있다.

/**
 * 이동 가능성이 보장되어 있는 Fish 에 대해서, 이동(swipe) 한다.
 * @param map 각 공간에 어떤 특정 물고기가 배치되어 있는지 알 수 있는 2중 array (얕은 복사로 물고기 위치 변경)
 * @param fishPosMap 각 물고기들이 num(번호)로 식별되어 살아있는지 확인하는 map (얕은 복사로 물고기의 Position 변경)
 * @param fish 현재 이동하려는 물고기 (이동 가능성 보장)
 */
static void swipeFish(Fish[][] map, Map<Integer, Position> fishPosMap, Fish fish) {
    Position fishPos = fishPosMap.get(fish.num);

    int x = fishPos.x + directions[0][fish.dir];
    int y = fishPos.y + directions[1][fish.dir];

    Fish newFish = map[x][y] != null ?
            new Fish(map[x][y].num, map[x][y].dir) : null;
    Position newFishPos = new Position(x, y);

    if (newFish == null) {
        map[x][y] = Fish.clone(fish);
        map[fishPos.x][fishPos.y] = null;

        fishPosMap.put(fish.num, newFishPos);
    }
    else {
        map[x][y] = Fish.clone(fish);
        map[fishPos.x][fishPos.y] = Fish.clone(newFish);

        fishPosMap.put(fish.num, newFishPos);
        fishPosMap.put(newFish.num, fishPos);
    }
}

 

기본적으로, Fish[][] map 과 Map<Interger, Position> fishPosMap 은 자료 구조이다. 이러한 자료 구조는 깊은 복사를 하지 않으면 얕은 복사가 되기때문에, 나는 이걸 역 이용할거다.

 

역 이용해서, 해당 swipeFish 메서드에서 두 객체의 내부 정보를 바꾸면, 이 메서드를 호출한 상위 메서드에서도 파라미터로 넣은 두 객체의 내부 정보가 바뀔 것(객체 참조 방식이기 때문에)이다. 

 

-> 이 관련 정보는 Java의 객체 참조 방식과 call by value + reference semantics 를 다룬 다음 포스팅에서 확인하자.

https://jinn-o.tistory.com/391

Java의 객체 참조 방식과 call by value + reference semantics

---

이제 전체 물고기는 이동한다. 각자의 삶의 방향에 맞게 ..

소제목이 좀 철학적인걸

/**
     * 현재 map 에서 살아있는 모든 물고기가 이동하고, 최종 map 을 return 한다.
     * @param map 현재 어항 상태
     * @param fishPosMap 살아있는 물고기 목록
     * @param sharkPos 상어의 위치
     * @return 최종적으로 변화하는 어항 상태
     */
    public static void movingFish(Fish[][] map, Map<Integer, Position> fishPosMap, Position sharkPos) {
        // 1 -> 16 moves in sequence
        for (int num=1; num<=16; num++) {
            if (!fishPosMap.containsKey(num)) continue;

            Position cur = fishPosMap.get(num); // current position
            Fish fish = map[cur.x][cur.y];  // current fish

            // fish is moving
            for (int i=0; i<8; i++) {
                // 방향대로 물고기가 갈 수 있나? -> 어항 범위 내에서 상어가 없어야함.
                if (canMoveFish(fish.dir, cur, sharkPos)) {
                    swipeFish(map, fishPosMap, fish);
                    break;
                }
                else {
                    // 갈 수 없다면, rotate
                    fish.rotate();
                }
            }
        }
    }

 

1번부터 16번의 물고기가 차례대로 이동할 것이다.

이때 어떤 물고기가 잡아먹히지 않고 살아있는지는, fishPosMap 에 저장될 것이다.

이 map 에 존재하지 않는다면.. 먹힌 거겠지!

 

다시 강조하지만, 이 때 swipeFish 메서드에서는 얕은 복사를 이용한다!

저렇게만 작성하고 swipeFish 메서드 내부에서 값을 변경해도 movingFish 메서드의 객체도 변경된다.

객체는 복사될 때, (깊은 복사를 하지 않으면) 참조하기 때문~~

 

canMoveFish 메서드 내에서는,

Fish 객체가 이동하려는 방향의 칸이 유효 범위에 존재하고,

그 칸에 상어가 있는지 없는지를 조사하는,

return type 이 Boolean 인 메서드이다.

---

이제부터 본격적인 DFS 시작이다. 상어를 이동시켜보자!

    /**
     * 물고기가 이동한 상태에서,
     * 상어가 이동 가능한 (최대 3가지의) 상태를 DFS 로 분기하고,
     * 분기 가능한 해당 각 상태에서 물고기를 먹은 상태를 반영하도록 한다.
     * 즉, 상어가 이동하는 DFS 메소드이다.
     * @param map 현재 어항 상태
     * @param fishPosMap 살아있는 물고기 목록
     * @param shark 상어 객체(누적 점수(num) 및 방향(dir))
     * @param sharkPos 상어의 위치
     */
    public static void movingAndEatingShark(Fish[][] map, Map<Integer, Position> fishPosMap, Fish shark, Position sharkPos) {

        movingFish(map, fishPosMap, sharkPos);

        int shark_x = sharkPos.x;
        int shark_y = sharkPos.y;

        // 방향에 있는 칸을 3칸까지 이동가능
        boolean isEaten = false;
        int movingCase = 3;
        while (movingCase -- > 0) {
            shark_x = shark_x + directions[0][shark.dir];
            shark_y = shark_y + directions[1][shark.dir];

            if (canMoveShark(shark_x, shark_y, map)) {
                isEaten = true;
                Fish eatenFish = map[shark_x][shark_y];

                Fish[][] eatenMap = deepCopyMap(map);
                eatenMap[shark_x][shark_y] = null;

                Map<Integer, Position> eatenFishPosMap = deepCopyPos(fishPosMap);
                eatenFishPosMap.remove(eatenFish.num);

                movingAndEatingShark(
                        eatenMap,
                        eatenFishPosMap,
                        new Fish(shark.num + eatenFish.num, eatenFish.dir),
                        new Position(shark_x, shark_y)
                );
            }
        }

        // 3칸 중에 하나라도 물고기가 없으면 집으로 돌아가 ~
        if (!isEaten) {
//            System.out.println("상어가 먹은 물고기 num 총합:" + shark.num);
            max_eating = Math.max(max_eating, shark.num);
        }
    }

 

왜 이 DFS 는 전부 깊은 복사를 했을까?

 

그 이유는 다음과 같다.

• 분기 가능한 상태가 최대 3가지뿐이기 때문. 맵은 4X4 로 고정이기 때문이다.
• 1번부터 16번의 물고기가 전부 순차대로 이동하는데, 그러면 map 의 상태가 너무나 많이 변화한다.

---

결론

• DFS 의 핵심은 분기점마다 `상태 변화` 를 어떻게 가져갈 것이냐가 관건이다!
• 상황에 따라 깊은 복사, 혹은 in-place + BackTracking 방식을 사용하자.
• 얕은 복사가 무조건 나쁜게 아니다! 잘 사용하면 객체를 자유자재로 변경할 수 있다.

후기

솔직히 이 문제 푸는데 며칠 걸리긴 했는데

정말정말정말 얻어가는게 많았다.

 

혼자 고민하고 왜 이렇게 적용해야할까를 생각하면서,

DFS 와 시뮬레이션에 대해 다시 생각해보게 된 계기가 되었다.

 

난 이제 DFS 가 두렵지 않다!!

 

최종 코드 통합본

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int[][] directions = { //  ↑, ↖, ←, ↙, ↓, ↘, →, ↗
            {-1, -1, 0, 1, 1, 1, 0, -1},
            {0, -1, -1, -1, 0, 1, 1, 1},
    };

    static String[] directions_string =
            {"↑", "↖", "←", "↙", "↓", "↘", "→", "↗"};

    static int max_eating = Integer.MIN_VALUE;

    public static void main(String[] args) throws IOException {
//        BufferedReader reader = new BufferedReader(new FileReader("src/shark.txt"));
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        Fish[][] map = new Fish[4][4];
        Map<Integer, Position> fishPosMap = new HashMap<>();

        int x_idx = 0;
        String line;
        while ((line = reader.readLine()) != null) {
            int[] list = Arrays.stream(line.split(" ")).mapToInt(Integer::parseInt).toArray();
            for (int i=0; i<8; i+=2) {
                int num = list[i];
                int dir = list[i+1] - 1;

                int y_idx = i/2;
                Position current = new Position(x_idx, y_idx);
                map[x_idx][y_idx] = new Fish(num, dir);
                fishPosMap.put(num, current);
            }
            x_idx++;
        }

//        printMap(map);

        Position startPos = new Position(0, 0);
        Fish startFish = map[startPos.x][startPos.y];

        Position sharkPos = new Position(startPos.x, startPos.y);
        Fish shark = new Fish(startFish.num, startFish.dir);

        // start point 에 있는 물고기는 먹히고 상어의 위치가 된다.
        map[startPos.x][startPos.y] = null;
        fishPosMap.remove(startFish.num);

        movingAndEatingShark(map, fishPosMap, shark, sharkPos);

//        printMap(map);
        System.out.println(max_eating);
    }

    /**
     * 물고기가 이동한 상태에서,
     * 상어가 이동 가능한 (최대 3가지의) 상태를 DFS 로 분기하고,
     * 분기 가능한 해당 각 상태에서 물고기를 먹은 상태를 반영하도록 한다.
     * 즉, 상어가 이동하는 DFS 메소드이다.
     * @param map 현재 어항 상태
     * @param fishPosMap 살아있는 물고기 목록
     * @param shark 상어 객체(누적 점수(num) 및 방향(dir))
     * @param sharkPos 상어의 위치
     */
    public static void movingAndEatingShark(Fish[][] map, Map<Integer, Position> fishPosMap, Fish shark, Position sharkPos) {

        movingFish(map, fishPosMap, sharkPos);

        int shark_x = sharkPos.x;
        int shark_y = sharkPos.y;

        // 방향에 있는 칸을 3칸까지 이동가능
        boolean isEaten = false;
        int movingCase = 3;
        while (movingCase -- > 0) {
            shark_x = shark_x + directions[0][shark.dir];
            shark_y = shark_y + directions[1][shark.dir];

            if (canMoveShark(shark_x, shark_y, map)) {
                isEaten = true;
                Fish eatenFish = map[shark_x][shark_y];

                Fish[][] eatenMap = deepCopyMap(map);
                eatenMap[shark_x][shark_y] = null;

                Map<Integer, Position> eatenFishPosMap = deepCopyPos(fishPosMap);
                eatenFishPosMap.remove(eatenFish.num);

                movingAndEatingShark(
                        eatenMap,
                        eatenFishPosMap,
                        new Fish(shark.num + eatenFish.num, eatenFish.dir),
                        new Position(shark_x, shark_y)
                );
            }
        }

        // 3칸 중에 하나라도 물고기가 없으면 집으로 돌아가 ~
        if (!isEaten) {
//            System.out.println("상어가 먹은 물고기 num 총합:" + shark.num);
            max_eating = Math.max(max_eating, shark.num);
        }
    }

    static Fish[][] deepCopyMap(Fish[][] map) {
        Fish[][] newMap = new Fish[4][4];
        for (int i=0; i<4; i++) {
            for (int j=0; j<4; j++) {
                Fish fish = map[i][j];
                if (fish == null) newMap[i][j] = null;
                else newMap[i][j] = new Fish(fish.num, fish.dir);
            }
        }
        return newMap;
    }

    static Map<Integer, Position> deepCopyPos(Map<Integer, Position> fishPos) {
        Map<Integer, Position> newFishPos = new HashMap<>();
        for (int key : fishPos.keySet()) {
            newFishPos.put(key, fishPos.get(key));
        }
        return newFishPos;
    }

    /**
     * 현재 map 에서 살아있는 모든 물고기가 이동하고, 최종 map 을 return 한다.
     * @param map 현재 어항 상태
     * @param fishPosMap 살아있는 물고기 목록
     * @param sharkPos 상어의 위치
     * @return 최종적으로 변화하는 어항 상태
     */
    public static void movingFish(Fish[][] map, Map<Integer, Position> fishPosMap, Position sharkPos) {
        // 1 -> 16 moves in sequence
        for (int num=1; num<=16; num++) {
            if (!fishPosMap.containsKey(num)) continue;

            Position cur = fishPosMap.get(num); // current position
            Fish fish = map[cur.x][cur.y];  // current fish

//            System.out.println(directions_string[fish.dir] + "(" + fish.dir + ")");
            // fish is moving
            for (int i=0; i<8; i++) {
                // 방향대로 물고기가 갈 수 있나? -> 어항 범위 내에서 상어가 없어야함.
                if (canMoveFish(fish.dir, cur, sharkPos)) {
                    swipeFish(map, fishPosMap, fish);
//                    printMap(map);
                    break;
                }
                else {
                    // 갈 수 없다면, rotate
                    fish.rotate();
//                    System.out.println(directions_string[fish.dir] + "(" + fish.dir + ")");
                }
            }
        }
    }

    /**
     * 이동 가능성이 보장되어 있는 Fish 에 대해서, 이동(swipe) 한다.
     * @param map 각 공간에 어떤 특정 물고기가 배치되어 있는지 알 수 있는 2중 array (얕은 복사로 물고기 위치 변경)
     * @param fishPosMap 각 물고기들이 num(번호)로 식별되어 살아있는지 확인하는 map (얕은 복사로 물고기의 Position 변경)
     * @param fish 현재 이동하려는 물고기 (이동 가능성 보장)
     */
    static void swipeFish(Fish[][] map, Map<Integer, Position> fishPosMap, Fish fish) {
        Position fishPos = fishPosMap.get(fish.num);

        int x = fishPos.x + directions[0][fish.dir];
        int y = fishPos.y + directions[1][fish.dir];

        Fish newFish = map[x][y] != null ?
                new Fish(map[x][y].num, map[x][y].dir) : null;
        Position newFishPos = new Position(x, y);

        if (newFish == null) {
            map[x][y] = Fish.clone(fish);
            map[fishPos.x][fishPos.y] = null;

            fishPosMap.put(fish.num, newFishPos);
        }
        else {
            map[x][y] = Fish.clone(fish);
            map[fishPos.x][fishPos.y] = Fish.clone(newFish);

            fishPosMap.put(fish.num, newFishPos);
            fishPosMap.put(newFish.num, fishPos);
        }
    }

    /**
     * 상어의 경우, 유효 범위 내에서 물고기가 있어야 함.
     */
    static boolean canMoveShark(int x, int y, Fish[][] map) {
        return inRange(x, y) && map[x][y] != null;
    }

    /**
     * 물고기의 경우, 유효 범위 내에서 상어가 없어야 함.
     */
    static boolean canMoveFish(int dir, Position fishPos, Position sharkPos) {
        int x = fishPos.x + directions[0][dir];
        int y = fishPos.y + directions[1][dir];

        return inRange(x, y) &&
                !(sharkPos.x == x && sharkPos.y == y);
    }

    static boolean inRange(int x, int y) {
        return 0<=x && x<4 && 0<=y && y<4;
    }

    static void printMap(Fish[][] map) {
        for (Fish[] list : map) {
            for (Fish fish : list) {
                System.out.print(fish);
            }
            System.out.println();
        }
        System.out.println();
    }
}

class Fish {
    int num;
    int dir;

    public Fish(int num, int dir) {
        this.num = num;
        this.dir = dir;
    }

    public static Fish clone(Fish fish) {
        return new Fish(fish.num, fish.dir);
    }

    public void rotate() {
        this.dir = (this.dir + 1) % 8;
    }

    @Override
    public String toString() {
        return String.format("%02d", num) +"(" + dir +") ";
    }
}

class Position {

    int x;
    int y;

    public Position(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString() {
        return "Position{" +
                "x=" + x +
                ", y=" + y +
                '}';
    }
}