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

삼성 작년 하반기 코테 오후 1번 문제이다.
실제로 봤었는데, 문제 유출이 정확히 이루어지지 않아서
실제 문제보단 약간 쉽다.
원래 문제는 물고기 시체랑 뭐랑 엄청 많았다.
자료구조도 엄청 생각해야 하고...

생각 흐름

삼성 문제는 자료구조부터 시작한다.
이번 문제를 푸려면 격자를 어떤 자료구조로 표현할 지 생각해야 한다.

격자에는 여러 변수가 들어간다.
물고기와 상어, 냄새 이렇게 세 가지이다.

삼성 문제는 1~n단계의 지시사항이 주어지고
이를 코드로 구현하는 것이다.
다만 코드로 구현할 때 전체 과정을 효율적으로 할 수 있도록 자료구조를 사용해야 한다.

각 단계를 어떻게 구현할 지 생각해 보자.

1. 복제 마법 시전

상어가 모든 물고기에게 복제 마법을 시전한다. 복제 마법은 시간이 조금 걸리기 때문에, 아래 5번에서 물고기가 복제되어 칸에 나타난다.

복제가 이뤄지는 시점 자체는 맨 처음에 일어난다.
다만 복제된 물고기가 실제로 생기는 것은 마지막 시점이다.
즉 1번 단계에서 복제할 물고기를 저장하는 변수가 있어야 한다는 뜻이다.

2. 물고기 이동

모든 물고기가 한 칸 이동한다. 상어가 있는 칸, 물고기의 냄새가 있는 칸, 격자의 범위를 벗어나는 칸으로는 이동할 수 없다. 각 물고기는 자신이 가지고 있는 이동 방향이 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전시킨다. 만약, 이동할 수 있는 칸이 없으면 이동을 하지 않는다. 그 외의 경우에는 그 칸으로 이동을 한다. 물고기의 냄새는 아래 3에서 설명한다.

방향 이동은 맨날 나온다.
반시계로 돈다고 하는데 시계든 반시계든 상관 없다.
어차피 dy, dx 배열 설정해놓고 인덱스를 1씩 빼주거나 더해주면 된다.

그러다가 이동할 수 있는 칸이 나오면 그때 실제로 이동을 하고 반복문을 멈추면 된다.

이동할 수 있는 칸이 없으면 안 한다는데,
반복문을 다 돌면 원상 복구 되도록 구현하면 신경 쓸 문제는 아니다.

문제는 물고기의 이동 자체인데,
여기서 물고기를 위한 자료구조를 어떻게 설계할 지 감이 온다.

냄새나 상어가 없는 칸으로 이동한다고 했으므로
한 칸에 여러 물고기가 있을 수 있다.
즉 물고기를 나타내기 위해선 4x4 배열의 벡터를 두어야 한다.

다만 물고기를 원래 자리에서 삭제하고 이동할 자리로 넣어야 하므로,
벡터 대신에 삽입/삭제가 자유로운 큐를 넣도록 한다.

두번째는 물고기가 이동하는 시점인데,
이동은 마지막에 한꺼번에 일어나야 한다.
이걸 나중에 알아채면 그냥 망했다고 보면 된다.

for문 돌면서 각 칸에 있는 모든 물고기 이동시키고, 옆칸 물고기들 다 이동시키고 할텐데
만약에 이전 칸에서 물고기가 바로 옆칸이나 밑의 칸으로 이동했다면
다음에 그 칸을 볼 때 또 이동하게 될 것이다.
즉 최악의 경우 물고기가 총 3번 연속으로 이동하는 대참사가 일어나게 된다.

이를 방지하기 위해 물고기를 실제로 이동시키는 게 아니라,
8방향 돌아가면서 이동 가능한 위치값이 나왔을 때,
그 위치값과 방향을 어디다 저장해놨다가 모든 물고기 이동이 끝나고 나서 그제서야 실제 물고기 큐에 추가해줘야 한다.

3. 상어 이동

상어가 연속해서 3칸 이동한다. 상어는 현재 칸에서 상하좌우로 인접한 칸으로 이동할 수 있다. 연속해서 이동하는 칸 중에 격자의 범위를 벗어나는 칸이 있으면, 그 방법은 불가능한 이동 방법이다. 연속해서 이동하는 중에 상어가 물고기가 있는 같은 칸으로 이동하게 된다면, 그 칸에 있는 모든 물고기는 격자에서 제외되며, 제외되는 모든 물고기는 물고기 냄새를 남긴다. 가능한 이동 방법 중에서 제외되는 물고기의 수가 가장 많은 방법으로 이동하며, 그러한 방법이 여러가지인 경우 사전 순으로 가장 앞서는 방법을 이용한다. 사전 순에 대한 문제의 하단 노트에 있다.

방향 개수가 달라진다.
상어의 방향 변수를 따로 써야 한다는 뜻이다.
연속으로 3번 이동하는데, 이동하는 중에 상어가 물고기를 먹게 된다.
이 먹는 물고기가 최대가 되는, 만약 그런 경우가 여러가지라면 그 중 사전 순으로 앞서는 순서로 이동하게 된다.

중복 순열을 사용하면 편할 것이다.
파이썬은 고맙게도 중복 순열 라이브러리가 있기 때문에 이는 어렵지 않을 것이다.

여기서 간과할 수 있는 것이
'상하상'으로 움직였을 때 한 칸이 중복으로 방문될텐데
이 때 먹은 물고기를 세면 안 된다는 것이다.
허나, 세지 못한다는 거지 이동이 불가능하다는 것은 아니다.
이게 이 문제의 실수 유발 포인트이다.

또한 문제를 잘 읽어보면 처음 상어가 이동하는 곳에선 아무런 일도 일어나지 않는다는 것을 알 수 있다.
왜냐면 연속해서 이동하는 중에, 같은 칸으로 이동하게 된다면이라고 했기 때문이다.
처음부터 같이 있는 건 이동 중에 만난 것이 아니므로 먹을 수가 없다.
이를 먹으려면 다른 데 갔다가 다시 와야 한다.
즉 시작하자 마자 중복 체크를 하면 안 된다.

상어의 이동은 다음과 같이 구현한다.
미리 구해둔 상어 이동 가능 시퀀스 (상상상 상상좌 ...) 를 돌면서
시퀀스 대로 시뮬레이션을 돌린다.
만약 가능한 이동 방법 (중간에 범위 안 벗어나는) 이라면 해당 방법을 문자열로 표현한 것과 잡아먹은 총 물고기 수를 '가능한 방향 시퀀스 후보군'에 저장한다.

후보군을 정렬해서, 가장 최적의 방향대로 실제로 이동한다.
실제로 이동할 땐 물고기들 다 잡아먹고 냄새도 뿌린다.

그리고 밑에 노트에 보면 상좌하우 인데
상하좌우로 헷갈리면 안 된다.

4. 냄새 빼기

두 번 전 연습에서 생긴 물고기의 냄새가 격자에서 사라진다.

냄새에 대해서 잘 생각해보자.
물고기는 확실히 한 칸에 여러 마리가 가능하다.
그럼 냄새도 한 칸에 여러 개여야 할까?

아니다. 냄새는 최대값으로 하나만 있으면 된다.
왜냐면 그 한 칸에 물고기 냄새가 하나 이상만 있어도 물고기가 못 가기 때문이다.
그래서 냄새는 4x4 정수 배열 하나만 있으면 된다.

이 과정은 그냥 냄새를 1씩 빼주면 된다.

5. 복제 완료

1에서 사용한 복제 마법이 완료된다. 모든 복제된 물고기는 1에서의 위치와 방향을 그대로 갖게 된다.

1번에서 따로 빼놨던 것들을 물고기 배열에 다시 추가해주면 될 것이다.

기타 조건

5에서 물고기 복제가 일어나고 나면,
상어가 있는 곳에 물고기가 생길 수 있다.
이에 대해, 그 자리엔 물고기가 안 생긴다거나 생기자마자 잡아먹혀서 냄새가 난다거나 하는 말이 없다.
대신 밑에 물고기와 상어가 같은 칸에 있을 수도 있다고 적혀 있다.

또한 그러한 물고기가 2번에서 이동을 못할 수도 있다.
이렇게 되면 3번 상어 이동할 때 물고기랑 같이 있을 수도 있다.

냄새 빼는 과정이 냄새 생긴 직후에 있다.
이때 바로 직전에 생긴 냄새를 또 제거해주면 안 된다.
제일 좋은 방법은 생성되는 냄새의 양을 2로 두지 않고 3으로 두는 것이다.

그래야 3번에서 냄새가 생겼을 때 4번에서 다시 2로 갈 수가 있다.

코드

from collections import deque
from itertools import product


# 격자 사이즈
SIZE = 4

# 물고기의 방향 종류
D_SIZE = 8

# 상어의 방향 종류
SD_SIZE = 4

# 상어가 나아갈 수 없음
IMPOSSIBLE = -1

# 물고기 냄새
FISH_SMELL = 3

# 물고기, 상어 방향
dy  = [0, -1, -1, -1,
       0, 1, 1, 1]

dx = [-1, -1, 0, 1,
      1, 1, 0, -1]

sdy = [-1, 0, 1, 0]
sdx = [0, -1, 0, 1]

# 물고기의 수, 상어가 마법을 연습한 횟수
M, S = 0, 0

# 격자에 있는 물고기 큐
fish = [[deque()]]

# 상어 위치
sx, sy = 0, 0

# 복사할 물고기들 큐
to_copy = deque()

# 격자의 물고기 냄새
smell = [[0]]

# 상어가 이동 가능한 모든 방향 시퀀스
possible_shark_direction_sequences = list(product([_ for _ in range(4)], repeat=3))


def solution():
    T = 1
    for t in range(T):
        tc()


def tc():
    # 전역변수 초기화 및 입력
    init()

    # S번 마법 연습 시전
    for i in range(S):
        do_magic()
        pass

    # 정답 출력
    answer = get_answer()
    print(answer)


# 전역변수 초기화 및 입력
def init():
    global M, S, fish, sx, sy, smell, to_copy
    M, S = map(int, input().split())
    fish = [[deque() for _ in range(SIZE)] for _ in range(SIZE)]

    for i in range(M):
        fx, fy, d = map(int, input().split())
        fy -= 1; fx -= 1; d -= 1
        fy, fx = fx, fy
        fish[fy][fx].append(d)

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

    to_copy = deque()
    smell = [[0 for _ in range(SIZE)] for _ in range(SIZE)]


def do_magic():
    prepare_to_copy()
    move_all_fish()
    move_shark_via_best_way()
    reduce_smell()
    copy_fish()
    pass


def prepare_to_copy():
    for i in range(SIZE):
        for j in range(SIZE):
            fish_count = len(fish[i][j])
            for k in range(fish_count):
                d = fish[i][j].popleft()
                to_copy.append((i, j, d))
                fish[i][j].append(d)


def move_all_fish():
    # 이동 시킬 물고기들
    to_move = []
    for i in range(SIZE):
        for j in range(SIZE):
            s = len(fish[i][j])
            for k in range(s):
                # 칸에서 물고기를 빼서 이동할 큐에 삽입
                d = fish[i][j].popleft()
                moved_y, moved_x, d = move_fish(i, j, d)
                to_move.append([moved_y, moved_x, d])

    # 이동시킬 물고기들을 실제로 이동시킴
    for my, mx, d in to_move:
        fish[my][mx].append(d)


def move_fish(i, j, d):
    moved_y, moved_x = i, j

    for l in range(D_SIZE):
        adj_y = i + dy[d]
        adj_x = j + dx[d]

        if is_fish_movable(adj_y, adj_x):
            moved_y, moved_x = adj_y, adj_x
            break

        d = (d - 1) % D_SIZE

    return moved_y, moved_x, d


def is_fish_movable(i, j):
    return is_valid(i, j) and \
           (sy, sx) != (i, j) and \
           smell[i][j] == 0


def is_valid(i, j):
    return 0 <= i < SIZE and 0 <= j < SIZE


def move_shark_via_best_way():
    global sy, sx
    d_seq_candidates = []

    # 상어가 이동할 수 있는 모든 방향 시퀀스대로 움직여 봄
    for d_seq in possible_shark_direction_sequences:
        ret = move_shark(d_seq)
        if ret is not None:
            eaten_fish_count, v_sy, v_sx, eaten_fish_pos = ret
            d_seq_candidates.append([-eaten_fish_count, "".join(list(map(str, d_seq))), v_sy, v_sx, eaten_fish_pos])

    d_seq_candidates.sort()

    # 후보군이 하나라도 있다면 먹은 물고기 수가 가장 크거나 사전 순으로 앞에 있는 방향대로 실제로 움직임
    if len(d_seq_candidates) >= 1:
        _, _, v_sy, v_sx, eaten_fish_pos = d_seq_candidates[0]
        sy, sx = v_sy, v_sx

        for fy, fx in eaten_fish_pos:
            fish[fy][fx].clear()
            smell[fy][fx] = FISH_SMELL


def move_shark(d_seq):
    global sy, sx
    eaten_fish_count = 0
    eaten_fish_pos = []
    v_sy, v_sx = sy, sx
    visited = [[False for _ in range(SIZE)] for _ in range(SIZE)]

    for d in d_seq:
        adj_y, adj_x = v_sy + sdy[d], v_sx + sdx[d]

        if not is_valid(adj_y, adj_x):
            return None

        if not visited[adj_y][adj_x]:
            visited[adj_y][adj_x] = True

            if fish[adj_y][adj_x]:
                eaten_fish_count += len(fish[adj_y][adj_x])
                eaten_fish_pos.append((adj_y, adj_x))

        v_sy, v_sx = adj_y, adj_x

    return eaten_fish_count, v_sy, v_sx, eaten_fish_pos


def reduce_smell():
    for i in range(SIZE):
        for j in range(SIZE):
            if smell[i][j] > 0:
                smell[i][j] -= 1


def copy_fish():
    while to_copy:
        fy, fx, d = to_copy.popleft()
        fish[fy][fx].append(d)


def get_answer():
    answer = 0

    for i in range(SIZE):
        for j in range(SIZE):
            answer += len(fish[i][j])

    return answer


solution()