중요 포인트:
1) DFS 호출 전 maps, d_list, fish_pos 전부 deepcopy해서 상어 이동시키고 dfs호출하기 (모든 경우를 실험해봐야 하므로 현재 상태를 복사해놔야 함)
2) 함수 호출 시 전역 변수 참조하지 않도록 인자 잘 넘기기 (현재 상태에 따라 리스트 상태가 모두 다르므로 전역 변수 참조하면 절대 안됨, 함수 만들 때 매개변수 어떤걸 받아야 하는지 잘 체크)
3) DFS 종료 조건 잘 세우고, 어떤 값을 리턴할건지 잘 생각하기
4) 물고기 먹을 때 maps나 d_list, fish_pos 갱신하면서 값이 이미 수정된 상태로 다른 값을 갱신하지 않는지 잘 체크하기 (temp같은 변수에 따로 값을 저장해서 수정하는 습관 들이기)
import copy
# 각 칸의 물고기 번호, 방향을 저장해야 함
# 0번은 상어, 1~16번은 물고기 방향 저장하는 배열
maps = [] # 0: 상어, 1~16: 물고기 번호, -1: 빈 곳
d_list = [0] * 17 # 값이 -1: 죽은 물고기
fish_pos = {}
for i in range(0, 4):
line = list(map(int, input().split()))
l = []
for j in range(0, 7, 2):
l.append(line[j])
fish_pos[line[j]] = [i, int(j / 2)] # 물고기의 x, y 좌표 저장
d_list[line[j]] = line[j + 1]
maps.append(l)
fishes = 0 # 잡아먹은 물고기의 번호
# 상어 (0, 0)에 넣기
fishes += maps[0][0]
d_list[0] = d_list[maps[0][0]]
d_list[maps[0][0]] = -1 # 죽은 물고기는 방향 삭제
maps[0][0] = 0
fish_pos[0] = [0, 0] # 상어 좌표 0에 추가
def get_dir(dir_num):
x = 0
y = 0
if dir_num == 1:
x = -1
y = 0
elif dir_num == 2:
x = -1
y = -1
elif dir_num == 3:
x = 0
y = -1
elif dir_num == 4:
x = 1
y = -1
elif dir_num == 5:
x = 1
y = 0
elif dir_num == 6:
x = 1
y = 1
elif dir_num == 7:
x = 0
y = 1
elif dir_num == 8:
x = -1
y = 1
return x, y
def turn_45(dir_num):
if dir_num == 8:
dir_num = 1
else:
dir_num += 1
return dir_num
def fish_move(maps, d_list, fish_pos):
# 낮은 번호부터 물고기 순서대로 이동
# 상어 위치 파악
shark_x, shark_y = fish_pos[0]
for i in range(1, 17):
if d_list[i] == -1: # 죽은 번호면 패스
continue
x, y = fish_pos[i]
turn_cnt = 0
while True:
dx, dy = get_dir(d_list[i])
nx, ny = x + dx, y + dy
# 한바퀴 돌고도(턴 호출할 때마다 횟수 카운팅, 8번 돌면) 이동할 곳이 없으면 패스
if turn_cnt >= 8:
break
# 상어가 있거나 맵 밖이라면 45도 턴하고 다시 체크
if (
0 > nx
or nx >= 4
or 0 > ny
or ny >= 4
or (shark_x == nx and shark_y == ny)
):
turn_cnt += 1
new_dir = turn_45(d_list[i]) # 45도 턴하고 방향 저장
d_list[i] = new_dir
continue
# 맵 밖으로 벗어나지 않고, 이동하려는 위치에 상어가 없다면
# 이동 가능함 - 1) 물고기가 있는 칸이거나 2) 빈 칸이거나
# 2) 빈 칸이면 그냥 이동
if maps[nx][ny] == -1:
maps[nx][ny] = i # 맵 갱신
maps[x][y] = -1
fish_pos[i] = [nx, ny] # 위치 갱신
break
# 1) 물고기 있는 칸이면 서로 위치 바꾸기
else:
fish_num = maps[nx][ny]
# 지금 물고기 갱신
maps[nx][ny] = i
fish_pos[i] = [nx, ny]
# 다른 물고기 갱신
fish_pos[fish_num] = [x, y]
maps[x][y] = fish_num
break
def dfs(maps, d_list, fish_pos, fishes):
# 전체 물고기 이동시키기
# 현재 상태 나타내는 인자들 잘 넘기기!! 전역변수 참조하지 않게 주의!!
fish_move(maps, d_list, fish_pos)
# 현재 상어의 위치와 방향을 가져오기
x, y = fish_pos[0]
dx, dy = get_dir(d_list[0])
keep_going = False
max_fish = 0
# 상어의 방향에 존재하는 모든 칸으로 이동 가능
for i in range(1, 4):
nx = x + (dx * i)
ny = y + (dy * i)
# 가고자 하는 칸이 맵 안에 존재하고, 빈칸이 아니라면 이동가능
if 0 <= nx < 4 and 0 <= ny < 4 and maps[nx][ny] != -1:
keep_going = True
# 현재 상태 복사해서 사용, deepcopy 사용해야 함!!
maps_copy = copy.deepcopy(maps)
d_list_copy = copy.deepcopy(d_list)
fish_pos_copy = copy.deepcopy(fish_pos)
# 복사본에서 상어 이동
eaten_fish = maps_copy[nx][ny]
fishes_new = eaten_fish + fishes # 먹은 물고기 누적
fish_pos_copy[0] = [nx, ny] # 상어 좌표 변경
maps_copy[nx][ny] = 0 # 상어 위치 이동
maps_copy[x][y] = -1 # 기존 위치는 빈공간으로 변경
# 먹은 물고기의 방향을 흡수
d_list_copy[0] = d_list_copy[eaten_fish]
d_list_copy[eaten_fish] = -1 # 먹은 물고기는 방향 삭제
# 복사본 수정한 걸로 dfs 호출
# dfs로부터 리턴된 fishes값과 현재 max_fish값 중 더 큰 값을 저장
max_fish = max(
max_fish, dfs(maps_copy, d_list_copy, fish_pos_copy, fishes_new)
)
# 상어가 더 이상 갈 곳이 없다면 현재까지 먹은 물고기 리턴하고 종료
if not keep_going:
return fishes
return max_fish # 경우의 수 중 fishes의 최댓값을 리턴
answer = dfs(maps, d_list, fish_pos, fishes)
print(answer)
