백준 23290 마법사 상어와 복제 (파이썬)

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

23290번: 마법사 상어와 복제

1. 문제의 방향 순서에 맞게 dx, dy를 정한다.

2. 냄새가 있는지 확인하는 smell 리스트와 물고기가 어느 방향으로 얼마나 있는지 저장하는 fish 리스트를 만든다

   fish 리스트에 입력받은 방향을 append한다.

   상어 좌표를 sx, sy에 저장한다

3. 나중에 복제 과정을 위해서 fish_before에 현재 fish를 복사한다

   한 물고기가 여러번 이동하는 것을 막기 위해서 fish_temp에 이동한 물고기를 기록하고 나중에 fish로 바꿔준다

4. 2번 과정을 위해서 반복문으로 모든 좌표를 검사한다

   현재 좌표에 물고기가 있으면 저장된 방향을 순서대로 불러와서 물고기를 이동시킨다

   조건에 맞게 이동 가능할 때까지 방향을 갱신한다

   이동가능하면 fish_temp에 방향을 append하고 flag를 1로 한 후 break한다

   만약 flag가 반복문을 끝내도 0이면 이동 불가능이므로 현재 좌표의 fish_temp에 방향을 다시 append한다

5. dfs로 사전 순 노트에 맞게 방향을 이동하면서 3번 과정에 맞게 이동 경로를 찾는다

   3번 과정을 위한 move_shark 함수는 좌표, 이동 횟수, 지운 물고기 수, 이동 경로, 중복 방지를 위한 check를 받는다

   다음 칸으로 이동 가능하면, 갱신해야할 값들을 갱신하고 초기화 하는 과정을 계속 반복한다

   지운 물고기가 있으면 해당 좌표를 check에 기록하면서, 상하상 같은 이동경로로 중복 제거하는 경우를 방지한다

   이동 횟수가 3일때, 지운 물고기가 이전 최대값을 넘게되면 이동 경로 move_dir을 갱신해준다.

6. move_dir에 저장된 방향을 하나씩 불러와서 상어를 이동시킨다

   경로에 물고기가 있으면 지워주고, 냄새를 기록한다

   냄새는 4번 과정을 위해서 전체 연습 시행 횟수로 저장해준다.

7. smell 리스트의 모든 좌표를 검사하면서, 두 번 전 연습에서 생긴 냄새를 제거해준다

8. fish_before에 있는 물고기를 fish에 append 해준다

9. 모든 과정이 끝나면 물고기 수를 출력해준다

import sys
from copy import deepcopy
from collections import deque

input = sys.stdin.readline
dx = [0, -1, -1, -1, 0, 1, 1, 1]
dy = [-1, -1, 0, 1, 1, 1, 0, -1]

smell = [[0] * 4 for _ in range(4)]
fish = [[[] for _ in range(4)] for _ in range(4)]
m, s = map(int, input().split())
for _ in range(m):
    x, y, d = map(int, input().split())
    fish[x-1][y-1].append(d-1)

sx, sy = map(int, input().split())
sx -= 1
sy -= 1


def move_shark(x, y, cnt, del_fish, direction, check):
    global max_del, move_dir
    if cnt == 3:
        if del_fish > max_del:
            move_dir = deepcopy(direction)
            max_del = del_fish
        return

    for d in [2, 0, 6, 4]:
        nx, ny = x + dx[d], y + dy[d]
        if not 0 <= nx < 4 or not 0 <= ny < 4:
            continue

        flag = 0
        if [nx, ny] in check:
            flag = 1
        if flag == 0:
            del_fish += len(fish[nx][ny])
        if fish[nx][ny]:
            check.append([nx, ny])
        cnt += 1
        direction.append(d)

        move_shark(nx, ny, cnt, del_fish, direction, check)

        if flag == 0:
            del_fish -= len(fish[nx][ny])
        if fish[nx][ny]:
            check.pop()
        cnt -= 1
        direction.pop()


for k in range(1, s+1):
    fish_before = deepcopy(fish)
    fish_temp = [[[] for _ in range(4)] for _ in range(4)]
    for i in range(4):
        for j in range(4):
            if fish[i][j]:
                for d in fish[i][j]:
                    flag = 0
                    for _ in range(8):
                        nx, ny = i + dx[d], j + dy[d]
                        if 0 <= nx < 4 and 0 <= ny < 4:
                            if not (nx == sx and ny == sy):
                                if smell[nx][ny] == 0:
                                    fish_temp[nx][ny].append(d)
                                    flag = 1
                                    break
                        d = (d + 7) % 8
                    if flag == 0:
                        fish_temp[i][j].append(d)
    fish = fish_temp

    max_del = -1
    move_shark(sx, sy, 0, 0, deque(), deque())

    x, y = sx, sy
    for d in move_dir:
        nx, ny = x + dx[d], y + dy[d]
        if fish[nx][ny]:
            fish[nx][ny] = []
            smell[nx][ny] = k
        x, y = nx, ny
    sx, sy = x, y

    for i in range(4):
        for j in range(4):
            if smell[i][j] > 0:
                if k - smell[i][j] == 2:
                    smell[i][j] = 0

    for i in range(4):
        for j in range(4):
            if fish_before[i][j]:
                for d in fish_before[i][j]:
                    fish[i][j].append(d)

ans = 0
for i in range(4):
    for j in range(4):
        ans += len(fish[i][j])
print(ans)