[BOJ][🟡2][백준#19236] 청소년 상어

문제 출처

BAEKJOON Online Judge #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>

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

입력

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

출력

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

예제

예제 1

입력

7 6 2 3 15 6 9 8
3 1 1 8 14 7 10 1
6 1 13 6 4 3 11 4
16 1 8 7 5 2 12 2

출력

33

예제 2

입력

16 7 1 4 4 3 12 8
14 7 7 6 3 4 10 2
5 2 15 2 8 3 6 4
11 8 2 4 13 5 9 4

출력

43

예제 3

입력

12 6 14 5 4 5 6 7
15 1 11 7 3 7 7 5
10 3 8 3 16 6 1 1
5 8 2 7 13 6 9 2

출력

76

예제 4

입력

2 6 10 8 6 7 9 4
1 7 16 6 4 2 5 8
3 7 8 6 7 6 14 8
12 7 15 4 11 3 13 3

출력

39

My Sol

def main():
    def copy_mat(mat):
        new_mat = [[[] for _ in range(4)] for _ in range(4)]
        for i in range(4):
            for j in range(4):
                new_mat[i][j] = mat[i][j][:]
        return new_mat

    def make_init_mat():
        mat = [[[] for _ in range(4)] for _ in range(4)]
        for i in range(4):
            lst = list(map(int, input().split()))
            for j in range(4):
                mat[i][j] = [lst[2*j], lst[2*j+1]]
        return mat


    def move_shark(i, j, di, dj, acc, mat):
        mat = move_fishes(mat)
        si, sj = i, j
        maxx = acc
        while True:
            si, sj = si+di, sj+dj
            if not (0<=si<4 and 0<=sj<4): break
            if not mat[si][sj]: continue
            fish_score = mat[si][sj][0]
            nsi, nsj = dirs[mat[si][sj][1]]
            new_mat = copy_mat(mat)
            new_mat[i][j] = []
            new_mat[si][sj][0] = 17
            maxx = max(maxx, move_shark(si, sj, nsi, nsj, acc+fish_score, new_mat))
        return maxx


    def move_fishes(mat):
        def move_fish(k):
            fi, fj = positions[k]
            fd = mat[fi][fj][1]
            for d in range(fd, 9):
                di, dj = dirs[d]
                si, sj = fi+di, fj+dj
                if not (0<=si<4 and 0<=sj<4): continue
                if not mat[si][sj]:
                    mat[si][sj] = [k, d]
                    mat[fi][fj] = []
                    return
                if mat[si][sj][0]==17: continue
                else:
                    tk, td = mat[si][sj]
                    positions[tk] = (fi, fj)
                    positions[k] = (k, d)
                    mat[si][sj] = [k, d]
                    mat[fi][fj] = [tk, td]
                    return

            for d in range(1, fd):
                di, dj = dirs[d]
                si, sj = fi+di, fj+dj
                if not (0<=si<4 and 0<=sj<4): continue
                if not mat[si][sj]:
                    mat[si][sj] = [k, d]
                    mat[fi][fj] = []
                    return
                if mat[si][sj][0]==17: continue
                else:
                    tk, td = mat[si][sj]
                    positions[tk] = (fi, fj)
                    positions[k] = (k, d)
                    mat[si][sj] = [k, d]
                    mat[fi][fj] = [tk, td]
                    return

        positions = {}
        for i in range(4):
            for j in range(4):
                if not mat[i][j]: continue
                if mat[i][j][0] == 17: continue
                positions[mat[i][j][0]] = (i, j)

        for k in sorted(positions.keys()):
            move_fish(k)

        return mat


    dirs = ((),(-1,0),(-1,-1),(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,1))
    mat = make_init_mat()
    init_score = mat[0][0][0]
    mat[0][0][0] = 17
    return move_shark(0, 0, *dirs[mat[0][0][1]], init_score, copy_mat(mat))

print(main())

단순한 구현 문제였다.

1. 상하좌우대각선의 방향의 델타값을 dirs에 저장했다.
2. [번호, 이동방향]의 배열을 각각 2차원 배열에 담은, 사실상 3차원 배열을 최초에 입력 받는다. 이를 make_init_mat으로 처리했다.
3. 상어가 위치하는 곳은 번호를 17로 하여 물고기의 이동에서 17의 번호를 피하는 방식으로 분기처리했다.
4. move_shark 함수에 왼쪽 최상단의 물고기의 크기와 방향을 인자로 넣어 상어의 이동을 시작했다. 이 과정에서 이동 좌표의 깊은 복사를 위해 copy_mat 함수를 통해 3차원 배열을 깊은 복사하여 함수 내부로 전달했다.
5. move_shark 함수에 진입하면 일단 상어가 한 번 이동했다는 전제로 진행하기 때문에, 바로 상어 이동 이후의 물고기의 이동을 한다. 이를 move_fishes 함수로 요약해, 이동 후의 3차원 배열을 받아 다시 저장한다.
6. move_fishes 함수는 일단 positions 라는 dictionary를 만든다. 이후 3차원 배열의 각 물고기 번호를 key, 좌표를 value로 저장한다. 이후 이 key들을 오름차순 정렬하여 낮은 물고기 번호 순으로 이동을 시작한다. 각 물고기는 move_fish 함수를 통해 이동한다.
7. move_fish 함수에서는 move_fishes 함수에서 구한 해당 물고기의 좌표를 기반으로, 저장된 이동 방향부터 반시계방향으로 조회하며 범위를 벗어나거나, 상어(17)가 있는 경우에는 다음 조회를 하고, 가능한 방향이라면 해당하는 좌표의 물고기와 좌표를 변경한다. 이는 3차원 배열과 position 모두에 반영된다. 이 과정을 모든 positions의 모든 물고기에 대해 진행하면 이후의 3차원 배열을 move_fishes 함수의 반환값으로 설정해 반환하는 것이다.
8. 다시 위에서 move_shark 직후 move_fishes로 물고기들이 이동했다면, 이제 다음 상어의 이동을 고려해 다음 move_shark를 할 차례이다. 상어는 이동방향의 모든 포인트마다 워프할 수 있는 경우의 수가 있으므로, 가능한 모든 경우에 대해 move_shark를 실행한다. 사실상 상어가 범위를 넘어서기 전까지의 모든 포인트마다 move_shark를 실행해주는 것이다. 이때 물고기가 없는 경우는 제외하고, 물고기가 있다면 해당하는 물고기 위치와 방향을 상어에 부여한 뒤, move_shark의 인자로 전달하며 다음 연결을 하는 것이다. 사실상 트리식, DFS의 구조이다.
9. 이렇게 현재 지점으로부터 이동할 수 있는 이후 경로에 대한 누적값 중 최댓값을 구하면 반환한다. 그렇다면 첫 move_shark의 반환값은 결국, 모든 경로에 대한 누적값의 최댓값인 것이다. 이를 main 함수에서 출력한다.

나름 2차원 배열을 깊은 복사하거나 N차 for문을 반복하는 방식이 있는만큼 소요시간을 걱정하기도 했다. 시간복잡도가 꽤나 높을 수 있기 때문이다. 하지만, 2차원 배열 자체도 4x4로 작은 크기이고, 효율적으로 이동 방향을 탐색했으며, 무엇보다 매번 물고기의 위치를 오름차순으로 좌표를 저장하는 방식을 선택해 메모리를 일부 사용하고 소요시간을 개선한 방식으로 작성한 결과 생각보다 너무나 빠른 풀이를 할 수 있었다.

결과

맞았습니다!!