2.py

importcopy

# 4 X 4 크기 격자에 존재하는 각 물고기의 번호(없으면 -1)와 방향 값을 담는 테이블
array= [[None] *4for_inrange(4)]

foriinrange(4):
data=list(map(int, input().split()))
# 매 줄마다 4마리의 물고기를 하나씩 확인하며
forjinrange(4):
# 각 위치마다 [물고기의 번호, 방향]을 저장
array[i][j] = [data[j*2], data[j*2+1] -1]

# 8가지 방향에 대한 정의
dx= [-1, -1, 0, 1, 1, 1, 0, -1]
dy= [0, -1, -1, -1, 0, 1, 1, 1]

# 현재 위치에서 왼쪽으로 회전된 결과 반환
defturn_left(direction):
return (direction+1) %8

result=0# 최종 결과

# 현재 배열에서 특정한 번호의 물고기 위치 찾기
deffind_fish(array, index):
foriinrange(4):
forjinrange(4):
ifarray[i][j][0] ==index:
return (i, j)
returnNone

# 모든 물고기를 회전 및 이동시키는 함수
defmove_all_fishes(array, now_x, now_y):
# 1번부터 16번까지의 물고기를 차례대로 (낮은 번호부터) 확인
foriinrange(1, 17):
# 해당 물고기의 위치를 찾기
position=find_fish(array, i)
ifposition!=None:
x, y=position[0], position[1]
direction=array[x][y][1]
# 해당 물고기의 방향을 왼쪽으로 계속 회전시키며 이동이 가능한지 확인
forjinrange(8):
nx=x+dx[direction]
ny=y+dy[direction]
# 해당 방향으로 이동이 가능하다면 이동 시키기
if0<=nxandnx<4and0<=nyandny<4:
ifnot (nx==now_xandny==now_y):
array[x][y][1] =direction
array[x][y], array[nx][ny] =array[nx][ny], array[x][y]
break
direction=turn_left(direction)

# 상어가 현재 위치에서 먹을 수 있는 모든 물고기의 위치 반환
defget_possible_positions(array, now_x, now_y):
positions= []
direction=array[now_x][now_y][1]
# 현재의 방향으로 쭉 이동하기
foriinrange(4):
now_x+=dx[direction]
now_y+=dy[direction]
# 범위를 벗어나지 않는지 확인하며
if0<=now_xandnow_x<4and0<=now_yandnow_y<4:
# 물고기가 존재하는 경우
ifarray[now_x][now_y][0] !=-1:
positions.append((now_x, now_y))
returnpositions

# 모든 경우를 탐색하기 위한 DFS 함수
defdfs(array, now_x, now_y, total):
globalresult
array=copy.deepcopy(array) # 리스트를 통째로 복사

total+=array[now_x][now_y][0] # 현재 위치의 물고기 먹기
array[now_x][now_y][0] =-1# 물고기를 먹었으므로 번호 값을 -1로 변환

move_all_fishes(array, now_x, now_y) # 전체 물고기 이동 시키기

# 이제 다시 상어가 이동할 차례이므로, 이동 가능한 위치 찾기
positions=get_possible_positions(array, now_x, now_y)
# 이동할 수 있는 위치가 하나도 없다면 종료
iflen(positions) ==0:
result=max(result, total) # 최댓값 저장
return
# 모든 이동할 수 있는 위치로 재귀적으로 수행
fornext_x, next_yinpositions:
dfs(array, next_x, next_y, total)

# 청소년 상어의 시작 위치(0, 0)에서부터 재귀적으로 모든 경우 탐색
dfs(array, 0, 0, 0)
print(result)