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

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

공부 날짜 : 2022.09.28
정답 참조 여부 : X

4x4의 공간에서 물고기가 방향에 맞춰 움직인뒤 상어가 물고기를 잡아먹고 물고기의 방향을 보존한다. 상어는 방향으로만 움직일 수 있으며 잡아먹을 물고기가 없어지면 집으로 돌아갈때 상어가 최대로 먹을 수 있는 물고기의 합을 구하는 문제이다.

---

dfs문제로 상어가 얼마나 이동하느냐에 따라 결과가 달라지는데 각 과정에서 상어의 상태를 보존하여 다음 깊이로 넘겨주며 잡아먹을 물고기가 없을때 잡아먹은 물고기수의 합을 갱신해주면 되는 문제였다.

---

문제자체가 어렵진 않았으나 함수가 이동하며 변수들이 어떻게 작용하는지를 정확히 몰라서 헤맸던 문제이다.

fish_move()함수를 실행하면 fish_move()의 지역변수로 fish,graph,shark가 없기때문에 당연히 함수를 호출한 깊이의 fish,graph,shark에 할당될것이라 생각했지만 그게 아니였다.

정확히 이해하기 위해서는 좀더 공부를 해봐야 겠지만
내가 의도한대로 하기 위해서 객체를 넘겨줘서 풀어야 하는듯 싶다.

소스코드

import sys
from copy import deepcopy
input = sys.stdin.readline
#######################################################
#데이터 입력받기

#바다 전체상황
graph = []

#물고기의 정보를 저장
fish = [0]*17

for i in range(4):
    a,a_dir, b,b_dir, c,c_dir, d,d_dir = map(int, input().split())
    #바다에는 물고기 번호만 저장
    graph.append([a,b,c,d])
    #물고기배열에 위치와 방향, 생존여부를 index번호에 맞게 방향 저장
    #문제에서 방향이 1부터 시작이므로 -1씩
    fish[a] = [i, 0, a_dir - 1, True]
    fish[b] = [i, 1, b_dir - 1, True]
    fish[c] = [i, 2, c_dir - 1, True]
    fish[d] = [i, 3, d_dir - 1, True]

    
#######################################################
#######################################################
  
#위쪽부터 반시계방향으로 45도씩
dx = [-1,-1,0,1,1,1,0,-1]
dy = [0,-1,-1,-1,0,1,1,1]

#######################################################
#######################################################
#물고기의 이동
def fish_move(fish,graph,shark):
    for i in range(1,17):
        if fish[i][3] == False:
            continue
    
        x, y, dir, _ = fish[i]
        
        #방향에따른 다음칸이 이동 가능할 때
        while True:
            nx = x + dx[dir]
            ny = y + dy[dir]
        
            if 0 <= nx < 4 and 0 <= ny < 4 and [nx, ny] != [shark[0], shark[1]]:
                break
                
            dir = (dir + 1) % 8
            
        #물고기 방향정보 갱신
        fish[i][2] = dir
            
        #물고기 정보에 담긴 위치를 바꿔줌
        fish[i][0], fish[i][1] = nx, ny
        fish[graph[nx][ny]][0], fish[graph[nx][ny]][1] = x,y
    
        #실제 바다의 위치를 바꿔줌
        graph[x][y], graph[nx][ny] = graph[nx][ny], graph[x][y]
 
#######################################################
#######################################################
#상어의 이동에 따른 dfs
def dfs(fish, graph, shark):
    global result
    
    fish_move(fish,graph,shark)
    
    #상어의 정보를 받아옴
    x, y, dir, eat_count = shark
    
    #상어가 이동할수 있는 공간이 있는지 판단하는 변수
    check_shark_move = False
    #최대거리 3까지 판단
    for i in range(1,4):
        nx = x + (i*dx[dir])
        ny = y + (i*dy[dir])
    
        # 범위 이내이고 먹을 수 있는 물고기가 있을때
        if 0 <= nx < 4 and 0 <= ny < 4 and fish[graph[nx][ny]][3]:
            #이동할 공간이 있으며
            check_shark_move = True
            
            #상어가 이동한 뒤
            shark[0], shark[1] = nx, ny
            #그 물고기의 방향을 가지고
            shark[2] = fish[graph[nx][ny]][2]
            #상어가 물고기를 먹어서
            shark[3] += graph[nx][ny]
            #그 칸의 물고기는 죽는다.
            fish[graph[nx][ny]][3] = False
            
            #위의 정보를 가지고 다음 깊이
            dfs(deepcopy(fish), deepcopy(graph), deepcopy(shark))
            
            #데이터 복구
            shark[0],shark[1] = x, y
            shark[2] = dir
            shark[3] = eat_count
            fish[graph[nx][ny]][3] = True
            
            
    #상어가 이동할 공간이 없다면 결과 갱신
    if check_shark_move == False:
        result = max(result, eat_count)
        return
    
#######################################################
#######################################################    
result = 0

#상어의 위치와 방향, 먹은 물고기 번호의 합을 저장하는 변수
#상어는 바다위에 있지않고 좌표 정보로만 판단됨
fish[graph[0][0]][3] = False
shark = [0, 0, fish[graph[0][0]][2], graph[0][0]]

dfs(deepcopy(fish), deepcopy(graph), deepcopy(shark))    
print(result)