[BOJ] 19236번 청소년 상어

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

19236번: 청소년 상어

import copy

EMPTY = -1

# 번호가 num인 물고기의 좌표를 찾는다. 없으면 (= 이미 먹혔으면) None을 return
def find_pos(arr, num):
    for i in range(4):
        for j in range(4):
            if arr[i][j][0] == num:
                return (i, j)

    return None


# 물고기의 방향을 바꾼다.
def turn_left(direction):
    return (direction+1)%8


# 물고기의 이동 구현. now_x, now_
def fish_move(arr, shark_x, shark_y):
    for i in range(1, 17):
        pos = find_pos(arr, i)
        if pos == None:
            continue
            
        x, y = pos
        direction = arr[x][y][1]
        
        for _ in range(8):
            nx = x+dx[direction]
            ny = y+dy[direction]
            
            if not (0<=nx<4 and 0<=ny<4):
                direction = turn_left(direction)
                continue
            
            if nx==shark_x and ny==shark_y:
                direction = turn_left(direction)
                continue
            
            arr[x][y][1] = direction
            arr[x][y], arr[nx][ny] = arr[nx][ny], arr[x][y]
            break
        
        
# 현재 상어가 이동할 수 있는 좌표들을 리스트로 반환한다.
def find_movable_pos(arr, shark_x, shark_y, direction):
    res = []
    
    for i in range(1, 4):
        nx, ny = shark_x+dx[direction]*i, shark_y+dy[direction]*i
        if not (0<=nx<4 and 0<=ny<4):
            continue
        
        if arr[nx][ny][0] == EMPTY:
            continue
        
        res.append((nx, ny))
        
    return res
    

def dfs(arr, total, shark_info):    # shark_info : (x, y, direction)
    global answer
    arr = copy.deepcopy(arr)
    
    shark_x, shark_y, direction = shark_info
    total += arr[shark_x][shark_y][0]
    arr[shark_x][shark_y][0] = EMPTY
    
    fish_move(arr, shark_x, shark_y)
    
    movable_pos = find_movable_pos(arr, shark_x, shark_y, direction)
    
    # 더 이상 이동할 수 있는 위치가 없다면 return
    if len(movable_pos) == 0:
        answer = max(answer, total)
        return
    
    for pos in movable_pos:
        nx, ny = pos
        info = (nx, ny, arr[nx][ny][1])
        dfs(arr, total, info)
        
    
arr = [[None]*4 for _ in range(4)]

for i in range(4):
    data = list(map(int, input().split()))
    for j in range(4):
        arr[i][j] = [data[2*j], data[2*j+1]-1]    # [물고기번호, 방향]

        
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, -1, -1, -1, 0, 1, 1, 1]

answer = 0
dfs(arr, 0, (0, 0, arr[0][0][1]))
print(answer)

1. direction이 1~8 로 표현되어 있는데, 애초에 맵에 원소들을 저장할 때 direction-1로 저장을 하면 편하다.

2. 함수마다 매개변수로 맵을 넣는게 안전하다. 안 그러면 레퍼런스가 꼬이는 일이 발생할 수도 있다. 시간절약!

3. 아직 DFS함수 구현이 서툴다. dfs함수를 처음 호출할 때 0으로 넣어서 호출. dfs 함수안에서 재귀적으로 부르기 전에 초기조건도 같이 구현하도록.

4. dfs 함수에서 shark_info는 '현재 상어의 위치' 의 개념으로 접근한게 아니라,  '상어가 다음에 이동할 위치'의 개념으로 접근한다. total도 거기서 더해버린다 

많이 어려운 문제였다.