[Baekjoon] 19236번 : 청소년 상어 - Python

Gold 2

19236번: 청소년 상어

 

문제 풀이

구현 + dfs 문제

 

우선 물고기가 번호 순서대로 이동해야 되기 때문에 리스트를 만들어 번호순으로 물고기 좌표를 저장해줬다.

그리고 재귀를 이용해 상어 먹기 - 물고기 이동 - 상어 이동을 반복해서 상어가 먹을 수 있는 최대 물고기 값을 계산해주었다. 

 

코드

from copy import deepcopy

fish = [[] for _ in range(17)]
mx = [-1, -1, 0, 1, 1, 1, 0, -1]
my = [0, -1, -1, -1, 0, 1, 1, 1]
num, direction = [], []
maxValue = -1

for i in range(4):
    temp = list(map(int, input().split()))
    num.append(temp[::2])
    direction.append(temp[1::2])

    for j in range(0, 7, 2):
        fish[temp[j]] = (i, j//2)

def dfs(s_x, s_y, total, fish, direction, num):
    global maxValue

    # 상어가 범위밖을 벗어나면
    if 0 > s_x or 0 > s_y or s_x >= 4 or s_y >= 4 or num[s_x][s_y] == 0:
        maxValue = max(maxValue, total)
        return

    # 상어 먹기
    fish[num[s_x][s_y]] = []
    s_d, direction[s_x][s_y] = direction[s_x][s_y] - 1, -1
    total += num[s_x][s_y]
    num[s_x][s_y] = 0

    # 물고기 이동
    for i in range(1, 17):
        # 먹히지 않았다면
        if fish[i]:
            x, y = fish[i][0], fish[i][1]
            d = direction[x][y] - 1

            # 상어이거나 범위를 벗어나면 계속 방향 변경
            while True:
                nx = x + mx[d]
                ny = y + my[d]

                if 0 <= nx < 4 and 0 <= ny < 4 and (nx, ny) != (s_x, s_y): break

                d = (d + 1) % 8

            direction[x][y] = d + 1

            if num[x][y]:
                fish[num[nx][ny]] = (x, y)

            fish[num[x][y]] = (nx, ny)
            direction[x][y], direction[nx][ny] = direction[nx][ny], direction[x][y]
            num[x][y], num[nx][ny] = num[nx][ny], num[x][y]

    # 상어 이동
    for i in range(3):
        nx = s_x + (mx[s_d] * (i+1))
        ny = s_y + (my[s_d] * (i+1))

        a, b, c = deepcopy(fish), deepcopy(direction), deepcopy(num)
        dfs(nx, ny, total, a, b, c)

dfs(0, 0, 0, fish, direction, num)
print(maxValue)

 

느낀점

이런 dfs문제를 풀때마다 디버깅에 시간이 오래걸리는 것 같다 ㅠㅠ

최대한 꼼꼼하게 문제를 읽고 로직을 짤 수 있게 노력해야겠다.