[백준 - Python] 19236 - 청소년 상어

0.  문제 링크

 

 

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

19236번: 청소년 상어

---

1.  풀이 방법

 

해당 문제에서 물고기의 값과 이동 방향은 복소수로 하나로 묶었다.

근데 딕셔너리를 쓰면 더 간단하게 풀 수 있을 것 같긴했는데, 이미 복소수로 묶어놔서 그냥 복소수로 풀었다.

우선 물고기의 움직임을 구현함 함수인 fish_move() 함수와 상어가 갈 수 있는 좌표를 반환하는 can_shark_move() 함수를 구현했다.

maps는 물고기와 상어의 위치를 나타냈다.

pos는 물고기 번호를 key로 해서, 물고기의 좌표를 저장했다.

cand는 먹을 수 있는 후보자들을 넣었다.

해당 문제에서 조금 실수했던 부분은, Mutable 객체를 인자로 넘기면 주소 값으로 넘겨져서, 어떤 변형을 하면 그게 새로운 객체에 적용되는 것이 아니라, 원래 객체가 변형되는 것이다.

해당 부분을 조금 실수해서 그냥 deepcopy로 문제를 해결했다.

 

자세한 설명은 주석에 써놓았으니, 참고 바랍니다.

---

2.  코드

 

 

import sys
from copy import deepcopy


def fish_move() -> (list, dict):
    # 물고기의 움직임을 구현한 함수
    global maps, pos

    for i in range(1, 17):
        # 1번부터 16번까지 물고기를 이동시킴
        if i in pos:
            y, x = pos[i]
            d = int(maps[y][x].imag)
            for _ in range(9):
                dy, dx = dir[d]
                ny, nx = y + dy, x + dx
                if 0 <= ny < 4 and 0 <= nx < 4:     # 범위를 벗어나지 않음
                    if maps[ny][nx] != -1:      # 상어가 없어야 함
                        maps[y][x], maps[ny][nx] = maps[ny][nx], complex(int(maps[y][x].real), d)        # 위치 교환
                        pos[i], pos[int(maps[y][x].real)] = [ny, nx], [y, x]     # 값 변경
                        break
                d = (d + 1) % 8


def can_shark_move(y : int, x : int, shark_dir : int) -> list:
    # 상어가 움직일 수 있는 공간을 반환함
    global maps

    cand = []
    dy, dx = dir[shark_dir]
    ny, nx = y + dy, x + dx
    while 0 <= ny < 4 and 0 <= nx < 4:
        if maps[ny][nx] != 0:        # 물고기가 있다면
            cand.append([ny, nx])
        ny, nx = ny + dy, nx + dx

    return cand


def sol(y : int, x : int, score : int, shark_dir : int) -> int:
    global maps, pos

    score += int(maps[y][x].real)       # 점수를 더함
    shark_dir = int(maps[y][x].imag)        # 상어의 방향을 구함
    pos.pop(int(maps[y][x].real))       # 해당 위치는 상어에게 먹힘

    maps[y][x] = -1     # 해당 자리에 상어가 있음

    fish_move()      # 물고기의 움직임
    cand = can_shark_move(y, x, shark_dir)       # 상어가 움직일 수 있는 곳

    maps[y][x] = 0      # 이제 상어는 이동해야 하므로, 해당 공간은 빈 공간이 됨

    maps_ori = deepcopy(maps)
    pos_ori = deepcopy(pos)
    score_list = []

    for (y, x) in cand:
        score_list.append(sol(y, x, score, shark_dir))
        maps = deepcopy(maps_ori)       # 맵 복구
        pos = deepcopy(pos_ori)     # 물고기 위치 복구

    if len(score_list) == 0:
        return score
    else:
        return max(score_list)


if __name__ == "__main__":
    input = sys.stdin.readline
    maps = [[0] * 4 for _ in range(4)]
    pos = dict()
    dir = [[-1, 0], [-1, -1], [0, -1], [1, -1], [1, 0], [1, 1], [0, 1], [-1, 1]]
    for i in range(4):
        temp = list(map(int, input().split()))
        for j in range(4):
            maps[i][j] = complex(temp[j * 2], temp[j * 2 + 1] - 1)
            pos[temp[j * 2]] = [i, j]

    print(sol(0, 0, 0, 0))

---

3.  마무리