https://www.acmicpc.net/problem/19236
상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 구해보자.
입력
첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 8보다 작거나 같은 자연수를 의미하고, 1부터 순서대로 ↑, ↖, ←, ↙, ↓, ↘, →, ↗ 를 의미한다.
출력
상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 출력한다.
# 19236 청소년 상어
def move_fish(idx, r, c, dir):
for i in range(8):
cur_dir = dir + i
if cur_dir >= 9:
cur_dir -= 8
cr = r + dr[cur_dir]
cc = c + dc[cur_dir]
# 범위 안에 있으면서 숫자가 맞을 경우
if 0 <= cr < 4 and 0 <= cc < 4 and 0 <= shark_fish[cr][cc][0] <= 16:
change_fish(r, c, cr, cc, cur_dir)
break
return
def change_fish(r, c, cr, cc, cur_dir):
temp_fish = shark_fish[r][c][0]
shark_fish[r][c] = shark_fish[cr][cc]
shark_fish[cr][cc] = [temp_fish, cur_dir]
return
# 0 상 좌상 좌 좌하 하 우하 우 우상
dr = [0, -1, -1, 0, 1, 1, 1, 0, -1]
dc = [0, 0, -1, -1, -1, 0, 1, 1, 1]
fishes = [[0] * 4 for _ in range(4)]
for i in range(4):
numbers = list(map(int, input().split()))
fishes[i][0] = [numbers[0], numbers[1]]
fishes[i][1] = [numbers[2], numbers[3]]
fishes[i][2] = [numbers[4], numbers[5]]
fishes[i][3] = [numbers[6], numbers[7]]
# 상어 표시
shark_dir = fishes[0][0][1]
temp_fish = [fish[:] for fish in fishes]
# r, c, dir, 잡아먹은 상어 숫자, 그 때의 fish 배열, level
shark_list = [[0, 0, shark_dir, temp_fish[0][0][0], temp_fish[:], 0]]
fishes[0][0][0] = 0 # 상어 표시
maximum_score = -1
while shark_list:
# 물고기 옮기기
shark_pos = shark_list.pop(0)
shark_r = shark_pos[0]
shark_c = shark_pos[1]
shark_dir = shark_pos[2]
shark_eat = shark_pos[3]
shark_fish = list()
for pos in shark_pos[4]:
temp_list = list()
for po in pos:
temp_list.append(po[:])
shark_fish.append(temp_list[:])
shark_level = shark_pos[5]
# 상어가 있던 곳 청소: -1을 0으로 만들어주기
for r in range(4):
for c in range(4):
if shark_fish[r][c][0] == -1:
shark_fish[r][c][0] = 0
# 상어가 현재 있는 곳을 -1로 만들어주기
shark_fish[shark_r][shark_c][0] = -1
# 물고기 이동
visited = [0] * 17
for idx in range(1, 17):
for r in range(4):
for c in range(4):
# 아직 이동하지 않은 물고기들 이동시키기
if shark_fish[r][c][0] == idx and visited[idx] == 0:
visited[idx] = 1
move_fish(idx, r, c, shark_fish[r][c][1])
break
# 상어 이동
# ori_shark_r = shark_r
# ori_shark_c = shark_c
while 0 <= shark_r < 4 and 0 <= shark_c < 4:
# 상어 이동
shark_r += dr[shark_dir]
shark_c += dc[shark_dir]
# 범위 안에 있고 잡아먹을 수 있는 곳이라면
if 0 <= shark_r < 4 and 0 <= shark_c < 4 and 1 <= shark_fish[shark_r][shark_c][0] < 17:
temp_fish = [shark[:] for shark in shark_fish]
# 상어가 잡아먹음
shark_eat = shark_pos[3] + temp_fish[shark_r][shark_c][0]
temp_shark_dir = temp_fish[shark_r][shark_c][1]
maximum_score = max(shark_eat, maximum_score)
shark_list.append([shark_r, shark_c, temp_shark_dir, shark_eat, temp_fish[:], shark_level + 1])
print(maximum_score)
소요시간: 50분 + 2시간 22분, 14:00 ~ 14:50, 22:16 ~ 00:40
틀린 부분 정리
처음에, 삼중 리스트를 쓸 생각을 하지 못했다.
상어가 물고기를 잡아먹은 결과판을 리스트 안에 들고 다니면서 계산하기까지 많은 시간이 소요되었다.
아이디어를 떠올리고 나서는, 물고기의 이동 함수와 상어가 이동하는 논리의 호환이 맞지 않았다. visited 리스트를 만드는 등 물고기를 이동시키는 함수를 다 구현한 뒤에 이 문제를 깨달았다.
물고기는 주어진 입력판인 fishes에서 움직이는데, 상어는 임의로 새로 만든 배열(위 코드엔 없다.)인 new_shark_list에서 움직였기 때문에, 상어가 물고기들을 잡아먹을 때 물고기의 움직임이 반영되지 않았다.
눈물을 머금고 물고기를 이동시키는 함수를 다시 건드렸다. 건드리기 전엔 대규모 공사가 예상되었는데, 다행히 생각보다 빠르게 정리되었다. 기존에 짰던 코드에서 살릴 수 있는 부분과, 응용할 수 있는 부분이 많아서 좋았다.
삼중리스트이기 때문에 deepcopy 문제가 발생할 것이라고 예상하였다.
이중리스트에서는 [temp[:] for temp in temp_list]와 같은 방식으로 deepcopy 문제를 해결했다. 결론만 얘기하면, 이는 기우였다. 삼중리스트를 사용하지만 삼중리스트에서 물고기, 상어가 배열되어 있는 배열판만 건드리면 됐기 때문에, 즉 이중리스트만 copy하면 됐기 때문에 위의 방식으로 해결할 수 있었다. 다만, 삼중리스트를 연구하는 과정에서 [te[:] for temp in temp_list for te in temp] 와 같은 방식으로 deepcopy 문제를 해결할 수 있다는 것도 알게 되었다.
while 0 <= shark_r < 4 and 0 <= shark_c < 4: 을 사용하여 상어가 이동할 수 있는 만큼 이동하였고, temp_fish를 사용하여 원 함수인 shark_fish가 계산 중 훼손되는 것을 방지하고자 하였다.
디버깅 중 상어가 현재 위치의 물고기를 두 번 먹는 에러가 있음을 인지하게 되었다. [1, 1]에 12번 물고기가 있었다면, 연산 과정에서 다음 점수는 24가 되는 식이었다. 이미 먹은 물고기를 다시 먹는 것은 있을 수 없는 일이므로, 코드에서 어느 부분이 잘못되었음을 알게 되었고 이를 찾아다녔다.
최초엔 물고기의 이동을 마치고 나서 상어 위치의 물고기 번호를 0으로 설정해주어 위의 문제를 해결하였다.
그러나, 문제 로직상 최초 상어가 [0, 0]에 들어간 뒤엔, 물고기가 상어의 눈치를 보며 이동해야 한다. 즉, 물고기를 이동시키기 전에 상어의 위치를 정해줘야 한다. 그래야 물고기들이 상어 위치에 들어가지 않는다. 회색 부분을 인지한 뒤 물고기가 이동하기 전, 상어 위치의 물고기 번호를 0으로 바꿔주었다. 예제 1, 2, 4번은 잘 돌아갔지만, 3번에서 58이라는 희한한 답이 나와 다시 디버깅을 하였다.
print를 많이 찍어보며, 물고기가 상어 자리도 자유롭게 돌아다닐 수 있음을 알게 되었다. 물고기가 이동하기 전에 상어의 위치에서 물고기 번호를 -1으로 바꿔주었다.
또다시 엉뚱한 출력이 나와 확인해보니, 상어가 이전에 있던 위치에서 물고기 번호가 -1로 남아있는 문제를 확인하였다. 물고기 번호가 -1인 부분을 모두 0으로 바꿔준 뒤에, 상어가 있는 곳만 물고기 번호를 0으로 바꿔주었고, 정답을 얻어낼 수 있었다.
삼중리스트 개념을 떠올리기 전에, 정말 어려웠다. 어떻게 원판을 보존할 수 있지?
삼중리스트를 보며 많이 좌절했다. 내가 풀 수 있을까?
삼중리스트를 해결하고 나서는, 물고기의 위치를 계속 데리고 다니며 물고기와 상어를 이동시키는 로직을 구상하며 정말 힘들었다. 어떻게 구현할 수 있지?
다 했다고 생각했는데, 답이 틀리게 나올 때도 절망스러웠다. 맞왜틀,,
비록 오랜 시간이 걸렸지만 무려 '백준 질문검색'을 참고하지 않고 푼 내 자신을 칭찬하고 싶다.
