[Samsung] 2020-1 오전 2번 술래잡기 체스

[Samsung] 2020-1 오전 2번 술래잡기 체스

Question

Language: Python

Difficulty: Gold 2

해당 문제의 풀이는 청소년 상어와 동일하다

Solution

from copy import deepcopy
#범위 확인
def check_range(row,col):
    if row < 0 or row>=4 or col < 0 or col>=4:
        return False
    return True

#도둑말을 움직이는 함수
def move_players(player_map,players,checked,chaser_row,chaser_col):
    for index in range(16):
        #이미 잡힌 도둑말인 경우
        if checked[index]:
            continue
        row,col,dir=players[index]

        #다음 위치에 갈 수 있을 때까지 회전 수행
        for i in range(8):
            next_dir=(dir+i)%8
            next_row=row+dy[next_dir]
            next_col=col+dx[next_dir]

            #격자 범위를 벗어나거나 다음 위치에 술래가 있는 경우 반시계 방향으로 45도 회전한다.
            if not check_range(next_row,next_col) or (next_row,next_col) == (chaser_row,chaser_col):
                continue
            
            next_player=player_map[next_row][next_col]
            players[index]=[next_row,next_col,next_dir]
            player_map[next_row][next_col],player_map[row][col]=player_map[row][col],player_map[next_row][next_col]

            #다음칸에 다른 도둑말이 있는 경우
            if next_player !=-1:
                players[next_player]=[row,col,players[next_player][2]]

            break  
        

#술래가 잡을 수 있는 도둑말의 위치들을 찾는다.
def find_players(player_map,row,col,dir):
    candidates=[]
    for i in range(1,4):
        next_row=row+dy[dir]*i
        next_col=col+dx[dir]*i
        
        #더 이상 도달 가능한 칸이 없다면 탈출한다.
        if not check_range(next_row,next_col):
            break
        
        #빈칸인 경우 넘어간다
        if player_map[next_row][next_col]==-1:
            continue
        
        candidates.append((next_row,next_col))
    
    return candidates

def print_board(title,board):
    print(title)
    for row in board:
        for col in row:
            print(col,end="\t")
        print()

def solution(index,player_map,players,checked,chaser_row,chaser_col,chaser_dir,point):
    global max_points
    #도둑말의 이동
    move_players(player_map,players,checked,chaser_row,chaser_col)

    #술래가 잡을 수 있는 도둑말들의 좌표를 찾아낸다.
    candidates=find_players(player_map, chaser_row,chaser_col,chaser_dir)

    #잡을 수 있는 도둑말에 대해서 잡아본다.
    for row,col in candidates:
        next_player=player_map[row][col]

        #다음 재귀문을 위한 새로운 배열 복사
        new_player_map=deepcopy(player_map)
        new_players=deepcopy(players)
        new_checked=deepcopy(checked)

        new_player_map[row][col]=-1
        new_checked[next_player]=True
        
        solution(index+1,new_player_map,new_players,new_checked,row,col,players[next_player][2],point+next_player+1)
    
    #해당 칸에서 술래가 잡을 수 있는 도둑말이 없는 경우 탈출한다.
    max_points=max(max_points,point)
    return
    
        
if __name__ == "__main__":

    player_map=[[-1] * 4 for _ in range(4)]
    players=[[] for _ in range(16)]
    checked=[False] * 16

    for row in range(4):
        temp=list(map(lambda x: int(x)-1,input().split()))
        for col in range(4):
            player_num,player_dir=temp[2*col], temp[2*col+1]
            players[player_num]=[row,col,player_dir]
            player_map[row][col]=player_num

    max_points=0

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

    #첫번째 좌표에 대한 처리 수행
    first_player=player_map[0][0]
    player_map[0][0]=-1
    checked[first_player]=True
    
    solution(0,player_map,players,checked,0,0,players[first_player][2],first_player+1)
    print(max_points)