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

https://www.acmicpc.net/problem/23290
골1 정도의 시뮬레이션 문제이다.

디버깅 2회 정도 때문에 3시간 정도 문제 풀이가 걸렸다.

문제에서 요구하는 바는 다음과 같다
1. 복제
2. 물고기 이동
3. 상어 이동
4. 잡아먹은 냄새 제거
5. 복제 업데이트

2, 3번에서 요구하는 조건들이 까다로워 시간이 조금 걸릴만한 문제이다.
필자는 상어가 방문한 곳은 방문하지 않도록 처리했더니 테케에서 통과가 안되어 질문 게시판의 힌트를 통해 고쳤다.
단순하게 이미 지나친 곳은 물고기가 없기 때문에 방문하면 안된다는 고정관념 때문에 오래 걸렸던 문제다.

import copy
from collections import deque

fish_num, practices = map(int, input().split())
fishes = [[[] for _ in range(4)] for _ in range(4)]
copy_fishes = []
fish_smell = [[0 for _ in range(4)] for _ in range(4)]

# 물고기의 방향
direction = [(0, -1), (-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1)]

# 상어의 방향
shark_dir = [(-1, 0), (0, -1), (1, 0), (0, 1)]

for _ in range(fish_num):
    row, col, d = map(int, input().split())
    fishes[row - 1][col - 1].append(d - 1)
shark_x, shark_y = map(int, input().split())
shark_x -= 1
shark_y -= 1


def move_fish():
    temp = [[[] for _ in range(4)] for _ in range(4)]
    for x in range(4):
        for y in range(4):
            for d in fishes[x][y]:  # 모든 물고기에 대하여
                nx, ny = x + direction[d][0], y + direction[d][1]
                cnt = 0
                original = d
                # 범위를 벗어나거나, 상어가 있거나, 냄새가 있는 곳은 못가기 때문에 반시계로 돌려준다.
                while nx < 0 or ny < 0 or nx >= 4 or ny >= 4 or (shark_x == nx and shark_y == ny) or fish_smell[nx][ny]:
                    d -= 1
                    nx, ny = x + direction[d][0], y + direction[d][1]
                    cnt += 1
                    # 모든 방향으로 못 움직일 경우 그대로 있는다.
                    if cnt >= 8:
                        d = original
                        nx, ny = x, y
                        break
                d = d % 8
                temp[nx][ny].append(d)
    return temp


def move_shark(shark_x, shark_y):
    q = deque()
    answer = -1
    visited = [[False for _ in range(4)] for _ in range(4)]
    history_result = ""
    q.append((shark_x, shark_y, 0, visited, ""))
    while q:
        # many: 잡아먹은 수, histroy: 방문처리, rseult: 방향 사전순 문자열
        x, y, many, history, result = q.popleft()
        if len(result) >= 3:
            # 제일 많이 잡아먹는 곳으로 가야하기 때문에 many가 더 크다면 갱신
            if many > answer:
                answer = many
                history_result = result
            # many가 같지만 사전순이 다를 수 있기 때문에 업데이트.
            elif many == answer:
                if history_result > result:
                    history_result = result
            continue
        for idx in range(4):
            nx, ny = x + shark_dir[idx][0], y + shark_dir[idx][1]
            if nx < 0 or ny < 0 or nx >= 4 or ny >= 4:
                continue
            # 이부분 때문에 질문 게시판 보고 반례를 찾았는데, 방문 했던 곳을 또 가도 된다.
            # 하지만, 카운팅은 하면 안된다.
            if history[nx][ny]:
                q.append((nx, ny, many, copy.deepcopy(history), result + str(idx + 1)))
            else:
                history[nx][ny] = True
                q.append((nx, ny, many + len(fishes[nx][ny]), copy.deepcopy(history), result + str(idx + 1)))
                history[nx][ny] = False
    # 문자열 저장해놓은 값 그대로 fish에 갱신 밑 fish_smell에 추가
    for order in history_result:
        nx, ny = shark_x + shark_dir[int(order) - 1][0], shark_y + shark_dir[int(order) - 1][1]
        if fishes[nx][ny]:
            fishes[nx][ny] = []
            fish_smell[nx][ny] = 2
        shark_x, shark_y = nx, ny
    # 상어 좌표 return
    return nx, ny


for _ in range(practices):
    # 복제
    copy_fishes = copy.deepcopy(fishes)
    fishes = move_fish()  # 물고기 이동
    # 2회 지난 냄새 제거
    for x in range(4):
        for y in range(4):
            if fish_smell[x][y]:
                fish_smell[x][y] -= 1
    shark_x, shark_y = move_shark(shark_x, shark_y)  # 상어 이동
    # 복제 업데이트
    for x in range(4):
        for y in range(4):
            for data in copy_fishes[x][y]:
                fishes[x][y].append(data)
result = 0
for x in range(4):
    for y in range(4):
        result += len(fishes[x][y])
print(result)