[BOJ] Q19236 청소년 상어

[BOJ] Q19236 청소년 상어

Question

Language: Python

Difficulty: Gold 2

문제에서 시뮬레이션에는 아래의 2가지가 동작한다.

1. 물고기의 이동
2. 상어의 이동

해당 문제을 풀이하기 위해 물고기에 대한 위치정보,방향 정보를 저정하는 fishes dictionary와 물고기가 있는 칸을 나타내는 board을 이용한다.

물고기의 이동

최대 8번의 방향 회전을 수행하는 것이 가능하며, 상어가 있는 칸이나 경계 밖을 넘어서는 칸에 대해서는 이동을 할 수 없다. 이동하려는 칸에 물고기가 있는 해당 물고기와 위치를 바꿔준다.

for iter in range(9):
    next_fish_dir=(fish_dir+iter)%8

    next_fish_row=fish_row + dy[next_fish_dir]
    next_fish_col=fish_col + dx[next_fish_dir]

만약 8번의 회전 이후에도 물고기가 이동할 수 없는 경우 원래의 방향으로 돌아오게 된다.(이를 위해 9번의 회전을 수행하도록 한다.)

target_fish_index=board[next_fish_row][next_fish_col]
board[next_fish_row][next_fish_col],board[fish_row][fish_col]=board[fish_row][fish_col],board[next_fish_row][next_fish_col]
fishes[i]=[next_fish_row,next_fish_col,next_fish_dir]  

#물고기가 있는 칸으로 이동시 이동하고자하는 칸에 있는 물고기에 대한 위치 정보를 바꿔줘야한다.
if target_fish_index!=0:
    fishes[target_fish_index]=[fish_row,fish_col,fishes[target_fish_index][2]]   
break

다른 칸에 물고기가 있는 경우, 해당 물고기에 대한 위치 정보를 최신화해야한다.

상어의 이동

상어는 상어의 이동 방향에 있는 물고기 중에서 원하는 것을 한 개 선택할 수 있다. 따라서, 상어의 이동 반경에 있는 물고기에 대한 위치 정보를 리스트로 저장해서, 각각의 물고기에 대해 dfs를 진행해야한다.

from copy import deepcopy

def find_move_spots(graph,shark_info):
    shark_row,shark_col,shark_dir=shark_info
    candidates=[]
    for i in range(1,4):
        next_row=shark_row+ dy[shark_dir] * i
        next_col=shark_col+ dx[shark_dir] * i
        
        #범위를 벗어나는 경우
        if next_row < 0 or next_row >=4 or next_col < 0 or next_col>=4:
            break

        #물고기가 없는 칸
        if graph[next_row][next_col] ==0:
            continue
        
        candidates.append((next_row,next_col))
    
    return candidates


def fish_moves(board,fishes,dead,shark_info):
    shark_row,shark_col,shark_dir=shark_info

    for i in range(1,17):
        #죽은 물고기는 생략
        if i in dead:
            continue

        fish_row,fish_col,fish_dir=fishes[i]
        #최대 8번의 회전 수행 가능
        for iter in range(9):
            next_fish_dir=(fish_dir+iter)%8

            next_fish_row=fish_row + dy[next_fish_dir]
            next_fish_col=fish_col + dx[next_fish_dir]
            
            #경계 밖의 칸
            if next_fish_row < 0 or next_fish_row>=4 or next_fish_col<0 or next_fish_col>=4:
                continue
            #상어가 있는 칸에는 이동 하지 않는다.
            if next_fish_row == shark_row and next_fish_col == shark_col:
                continue

            target_fish_index=board[next_fish_row][next_fish_col]
            board[next_fish_row][next_fish_col],board[fish_row][fish_col]=board[fish_row][fish_col],board[next_fish_row][next_fish_col]
            fishes[i]=[next_fish_row,next_fish_col,next_fish_dir]  

            #물고기가 있는 칸으로 이동시 이동하고자하는 칸에 있는 물고기에 대한 위치 정보를 바꿔줘야한다.
            if target_fish_index!=0:
                fishes[target_fish_index]=[fish_row,fish_col,fishes[target_fish_index][2]]   
            break


def dfs(board,fishes,shark_info,dead,result):
    global max_result
    
    #물고기 이동을 진행하고
    fish_moves(board,fishes,dead,shark_info)
    #상어가 먹을 수 있는 물고기가 있는지 찾는다.
    candidates=find_move_spots(board,shark_info)

    if len(candidates) ==0:
        max_result=max(max_result,result)
        return
    
    #먹이를 찾아서 이동한다.
    for row,col in candidates:
        temp_board=deepcopy(board)
        temp_fishes=deepcopy(fishes)
        target_index=temp_board[row][col]
        temp_board[row][col]=0
        dfs(temp_board,temp_fishes,[row,col,fishes[target_index][2]],dead+[target_index],result+target_index)      
    

def solution(board,fishes):
    first_index=board[0][0]
    shark_info=[0,0,fishes[first_index][2]]
    #첫 번째는 먹이는 잡아 먹히게 된다.
    board[0][0]=0
    dfs(board,fishes,shark_info,[first_index],first_index)


if __name__== "__main__":
    board=[[0]*4 for _ in range(4)]
    fishes=dict()
    dy=[-1,-1,0,1,1,1,0,-1]
    dx=[0,-1,-1,-1,0,1,1,1]
    max_result=0
    for row in range(4):
        temp=list(map(int,input().split()))

        for col in range(4):
            index,dir=temp[col*2],temp[col*2+1]-1
            fishes[index]=[row,col,dir]
            board[row][col]=index
            
    solution(board,fishes)
    print(max_result)