[BOJ] 19236 - 청소년 상어 (Python)

 

 

아이디어

 

깊은 복사로 공간 정보를 넘기며 DFS로 상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 구한다.

 

 

풀이

 

delta = [(-1, 0), (-1, -1), (0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 1)]

def dfs(fish, board, total):
    global res
    for i in range(1, 17):
        if fish[i]:
            r, c, d = fish[i]
            dr, dc = delta[d]
            nr, nc = r+dr, c+dc
            while 1:
                if 4 > nr >= 0 and 4 > nc >= 0 and board[nr][nc] != -1:
                    board[r][c], board[nr][nc] = board[nr][nc], i
                    if fish[board[r][c]]:
                        fish[board[r][c]], fish[i] = fish[i], fish[board[r][c]]
                        fish[board[r][c]][2], fish[i][2] = fish[i][2], fish[board[r][c]][2]
                    else:
                        fish[i] = [nr, nc, d]
                    break
                else:
                    fish[i][2] = d = (d+1)%8
                    dr, dc = delta[d]
                    nr, nc = r+dr, c+dc
    r, c, d = fish[-1]
    dr, dc = delta[d]
    nr, nc = r+dr, c+dc
    board[r][c] = 0
    while 4 > nr >= 0 and 4 > nc >= 0:
        if fish[board[nr][nc]]:
            temp = board[nr][nc]
            _board = [board[i][:] for i in range(4)]
            _fish = [fish[i][:] for i in range(18)]
            _fish[-1] = [nr, nc, fish[temp][2]]
            _fish[temp].clear()
            _board[nr][nc] = -1
            dfs(_fish, _board, total+temp)
        nr += dr
        nc += dc
    if total > res:
        res = total

fish = [[] for _ in range(18)]
board = [[0]*4 for _ in range(4)]
for r in range(4):
    temp = tuple(map(int, input().split()))
    for c in range(4):
        fish[temp[c*2]] = [r, c, temp[c*2+1]-1]
        board[r][c] = temp[c*2]
fish[-1] = [0, 0, fish[board[0][0]][2]]
fish[board[0][0]] = []
res = board[0][0]
board[0][0] = -1
dfs(fish, board, res)
print(res)