[Python] 백준 23290 마법사 상어와 복제

https://www.acmicpc.net/problem/23290

# 23290 마법사 상어와 복제

def move_fish(shark_r, shark_c):
    global grounds
    temp_grounds = list()
    for r in range(1, 5):
        for c in range(1, 5):
            for idx in range(1, 9):
                if grounds[r][c][idx]:
                    direction = idx
                    orig_direction = direction
                    for _ in range(8):
                        cr = r + dr[direction]
                        cc = c + dc[direction]
                        # 범위 내에 있으면서 상어도 없고 냄새도 없다면
                        if 1 <= cr <= 4 and 1 <= cc <= 4 and (cr != shark_r or cc != shark_c) and smell[cr][cc] == 0:
                            temp_grounds.append([cr, cc, direction, grounds[r][c][idx]])
                            break
                        else:
                            direction -= 1
                            if direction <= 0:
                                direction += 8
                    # 그 자리에 있기
                    else:
                        temp_grounds.append([r, c, orig_direction, grounds[r][c][idx]])

    grounds = [[[0] * 9 for _ in range(5)] for _ in range(5)]
    for tr, tc, tdirection, num in temp_grounds:
        grounds[tr][tc][tdirection] += num
    return

#     0 좌 좌상 상 우상 우 우하 하 좌하
dr = [0, 0, -1, -1, -1, 0, 1, 1, 1]
dc = [0, -1, -1, 0, 1, 1, 1, 0, -1]

# 0, 상 좌 하 우
shark_dr = [0, -1, 0, 1, 0]
shark_dc = [0, 0, -1, 0, 1]

M, S = map(int, input().split())
grounds = [[[0] * 9 for _ in range(5)] for _ in range(5)]
smell = [[0] * 5 for _ in range(5)]
for _ in range(M):
    r, c, d = map(int, input().split())
    grounds[r][c][d] += 1

shark_r, shark_c = map(int, input().split())

for idx in range(1, S + 1):

    # 1. 상어가 모든 물고기에 복제 마법 시전
    copy_list = [[[0] * 9 for _ in range(5)] for _ in range(5)]
    for r in range(1, 5):
        for c in range(1, 5):
            for i in range(1, 9):
                copy_list[r][c][i] = grounds[r][c][i]

    # 2. 모든 물고기가 한 칸 이동
    move_fish(shark_r, shark_c)

    # 3. 상어가 연속해서 3칸 이동한다. 가장 물고기를 많이 먹을 수 있는 방법으로 이동
    # 경우의 수가 많다면 사전 순으로
    choice = list()
    maximum = 0
    temp_shark_r = 0
    temp_shark_c = 0

    temp_grounds_list = [[[0] * 9 for _ in range(5)] for _ in range(5)]
    for r in range(1, 5):
        for c in range(1, 5):
            for i in range(1, 9):
                temp_grounds_list[r][c][i] = grounds[r][c][i]

    for i in range(1, 5):
        cr1 = shark_r + shark_dr[i]
        cc1 = shark_c + shark_dc[i]
        if cr1 <= 0 or cr1 >= 5 or cc1 <= 0 or cc1 >= 5:
            continue
        sum1 = sum(temp_grounds_list[cr1][cc1])
        temp_grounds_list[cr1][cc1] = [0] * 9
        for j in range(1, 5):
            cr2 = cr1 + shark_dr[j]
            cc2 = cc1 + shark_dc[j]
            if cr2 <= 0 or cr2 >= 5 or cc2 <= 0 or cc2 >= 5:
                continue
            sum2 = sum(temp_grounds_list[cr2][cc2])
            temp_grounds_list[cr2][cc2] = [0] * 9
            for k in range(1, 5):
                cr3 = cr2 + shark_dr[k]
                cc3 = cc2 + shark_dc[k]
                if cr3 <= 0 or cr3 >= 5 or cc3 <= 0 or cc3 >= 5:
                    continue

                sum3 = sum(temp_grounds_list[cr3][cc3])
                # 물고기 최대로 많이 먹을 수 있는 방법
                if sum1 + sum2 + sum3 > maximum:
                    maximum = sum1 + sum2 + sum3
                    choice = [[cr1, cc1], [cr2, cc2], [cr3, cc3]]
                    temp_shark_r = cr3
                    temp_shark_c = cc3

                # 물고기 못먹을 때 방지
                if choice == []:
                    choice = [[cr1, cc1], [cr2, cc2], [cr3, cc3]]
                    temp_shark_r = cr3
                    temp_shark_c = cc3
            for i in range(1, 9):
                temp_grounds_list[cr2][cc2][i] = grounds[cr2][cc2][i]
        for i in range(1, 9):
            temp_grounds_list[cr1][cc1][i] = grounds[cr1][cc1][i]

    shark_r = temp_shark_r
    shark_c = temp_shark_c

    # 상어 이동, 물고기 제거됐다면 냄새를 남긴다.
    for cr, cc in choice:
        if sum(grounds[cr][cc]) > 0:
            # 물고기 먹기
            grounds[cr][cc] = [0] * 9
            smell[cr][cc] = idx

    # 4. 두 번 전 연습에서 생긴 물고기의 냄새가 격자에서 사라진다.
    for r in range(1, 5):
        for c in range(1, 5):
            if smell[r][c] + 2 <= idx:
                smell[r][c] = 0

    # 5.1에서 사용한 복제 마법이 완료된다.
    for r in range(1, 5):
        for c in range(1, 5):
            for i in range(1, 9):
                grounds[r][c][i] += copy_list[r][c][i]


# 숫자 세기
result = 0
for r in range(1, 5):
    for c in range(1, 5):
        for k in range(1, 9):
            result += grounds[r][c][k]

print(result)

헤맨 부분

문제 푸느라 너무 힘들었다.. 쉬는 시간 포함 세 시간 가량을 썼다.

상어가 연속해서 3칸을 이동할 때, 재귀 대신 3중 for문을 이용하여 계산하였다.
맨 처음엔 cr1 == cr3, cc1 == cc3처럼 조건에 맞지 않는 경우에만 continue하여 문제를 풀려 했으나, 잘 되지 않았다.
그래서 visited를 이용하여 방문했던 곳은 방문하지 않도록 만드려고 했으나, 마음만큼 잘 동작하지 않았다.
결정적으로, visited를 사용하면 되지 않는 예시가 있었다. 방문했던 곳이라도, maximum하게 생선을 먹을 수 있으며 사전순으로 앞쪽이라면 다시 방문해야 한다. 백준의 예제 입력 6번에서, visited를 사용하면 답으로 12가 출력된다. 방문했던 곳의 재방문을 허용해야 한다.

재방문을 허용하는 동시에, 재방문했을 경우 물고기의 score가 더해지면 안 된다. 이미 먹은 물고기이기 때문이다. 그렇다고 원본 grounds의 값을 수정할수도 없으므로, temp_grounds_list를 만들어 사용하였다.

문제에서 시키지 않았던 작업도 했었다. 상어 이동 후에 shark_r, shark_c의 물고기를 없애주는 작업도 해봤는데, 예제 5번, 8번에서 엉뚱한 정답이 출력되어 그만두었다.

다 풀고나서 제출했는데, 시간초과가 떴다. 맞왜틀,,,,,,,,,,

백준 질문 게시판에서 답을 찾을 수 있었다. list에 생선 방향을 계속 달고 다니기 때문이라고 한다. 생선을 리스트에 넣는 대신, 생선 숫자를 count한 list를 갖고 다니면 된다. 옛날에 배운 count 정렬이 생각난다.

생선 숫자를 count한 list를 갖고 다니라는 것은, 코드에서 grounds를 다 뜯어고쳐야 한다는 뜻이기도 하다. 고통의 시간 뒤에 코드를 뜯어고쳤고, 제출 후 정답 안내를 받았다.

문제를 잘 풀고 있지만, 소요 시간이 많이 걸리는 점이 다소 아쉽다.

화이팅!