문제링크
공간은 4x4로 고정한다.
각 물고기들은 차례마다 대각선을 포함한 8개 방향으로 한 칸씩 움직인다.
상어는 무조건 (0, 0)에 있는 물고기를 먹으며 시작하며, 먹은 물고기의 방향을 그대로 이어간다.
상어는 방향은 고정이나 이동거리는 공간 내라면 상관없고, 다음 방향이 공간 밖으로 이동하거나 먹을 수 있는 물고기가 존재하지 않는다면 끝난다.
상어가 획득할 수 있는 점수의 최대를 구하시오.
점수는 상어가 잡아먹은 물고기의 번호만큼 획득한다.
해당 문제는 DFS를 활용해 풀 수 있다. 하지만 물고기의 이동을 구현하는데 있어 방향을 바꿔주는 것이 까다롭게 느껴질 수 있다.
array를 전역으로 선언한 뒤, 안에서 활용할 때 3차례에 대해 DFS를 접근하면서 값이 변경되지 않도록 copy.deepcopy를 활용해 따로 넣어주는 것이 중요하다!
import copy
# 4 x 4 크기의 정사각형에 존재하는 각 물고기의 번호(없으면 -1)와 방향 값을 담는 테이블
array = [[None] * 4 for _ in range(4)]
for i in range(4):
data = list(map(int, input().split()))
# 매 줄마다 4마리의 물고기를 하나씩 확인하며
for j in range(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]
# 현재 위치에서 왼쪽으로 회전된 결과 반환
def turn_left(direction):
return (direction + 1) % 8
result = 0 # 최종결과
# 현재 배열에서 특정한 번호의 물고기 위치 찾기
def find_fish(array, index):
for i in range(4):
for j in range(4):
if array[i][j][0] == index:
return (i, j)
return None
# 모든 물고기를 회전 및 이동시키는 함수
def move_all_fishes(array, now_x, now_y):
# 1번부터 16번까지의 물고기를 차례대로 (낮은번호부터) 확인
for i in range(1, 17):
# 해당 물고기의 위치 찾기
position = find_fish(array, i)
if position != None:
x, y = position[0], position[1]
direction = array[x][y][1]
# 해당 물고기의 방향을 왼쪽으로 계속 회전시키며 이동이 가능한지 확인
for _ in range(8):
nx = x + dx[direction]
ny = y + dy[direction]
# 해당 방향으로 이동이 가능하다면 이동시키기
if 0 <= nx and nx < 4 and 0 <= ny and ny < 4:
if not (nx == now_x and ny == now_y):
array[x][y][1] = direction
array[x][y], array[nx][ny] = array[nx][ny], array[x][y]
break
direction = turn_left(direction)
def get_possible_positions(array, now_x, now_y):
positions = []
direction = array[now_x][now_y][1]
# 현재의 방향으로 계속 이동시키기
for i in range(4):
now_x += dx[direction]
now_y += dy[direction]
# 범위를 벗어나지 않는지 확인하며
if 0 <= now_x and now_x < 4 and 0 <= now_y < 4 :
# 물고기가 존재하는 경우
if array[now_x][now_y][0] != -1:
positions.append((now_x, now_y))
return positions
# 모든 경우를 탐색하기 위한 DFS 함수
def dfs(array, now_x, now_y, total):
global result
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)
# 이동할 수 있는 위치가 없다면 종료
if len(positions) == 0:
result = max(result, total) # 최댓값 저장
return
# 모든 이동할 수 있는 위치로 재귀적 수행
for next_x, next_y in positions:
dfs(array, next_x, next_y, total)
# 청소년 상어의 시작 위치(0, 0)에서부터 재귀적으로 모든 경우 탐색
dfs(array, 0, 0, 0)
print(result)
물고기의 이동에서 방향을 바꿔주는 부분에서 무한루프가 계속돌아 고생했다. 구현에 조금 더 노력하자!
해당 문서는 '이것이 코딩 테스트다.with 파이썬 - 나동빈 저'를 공부하고 정리한 글입니다.