[Python / BOJ 23290] 마법사 상어와 복제

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

23290번: 마법사 상어와 복제

 

문제

• 4 × 4 크기의 격자. 격자의 가장 왼쪽 윗 칸은 (1, 1)
• 물고기는 M마리, 8가지의 이동방향(상하좌우, 대각선) 중 하나를 가지고 있다.
• 상어는 1마리, 4가지의 이동방향(상하좌우) 중 하나를 가지고 있다.
• 둘 이상의 물고기가 같은 칸에 있을 수도 있으며, 마법사 상어와 물고기가 같은 칸에 있을 수도 있다.

 

상어의 마법 연습 한 번은 다음과 같은 작업이 순차적으로 이루어진다. S번 연습을 모두 마쳤을때, 격자에 있는 물고기의 수는?

1. 상어가 모든 물고기에게 복제 마법을 시전한다. 복제 마법은 시간이 조금 걸리기 때문에, 5번에서 물고기가 복제된다.
2. 모든 물고기가 한 칸 이동한다. 상어가 있는 칸, 물고기의 냄새가 있는 칸, 격자의 범위를 벗어나는 칸으로는 이동할 수 없다. 각 물고기는 자신이 가지고 있는 이동 방향이 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전시킨 후 이동한다.
3. 상어가 연속해서 3칸 이동한다. 상어는 현재 칸에서 상하좌우로 인접한 칸으로 이동할 수 있다. 연속해서 이동하는 칸 중 격자 범위를 벗어나면 해당 방법은 불가능하다. 이동하는 중 물고기가 있는 칸을 지나면 해당 물고기는 사라지고, 냄새를 남긴다. 가능한 이동 방법 중 없애는 물고기가 가장 많은 방법으로 이동하고, 여러개면 사전 순으로 앞선 방법을 택한다.
   • 4^3 = 64가지 방법을 사전 순으로 나열해보면 [상, 상, 상], [상, 상, 좌], [상, 상, 하], [상, 상, 우], [상, 좌, 상], [상, 좌, 좌], [상, 좌, 하], [상, 좌, 우], [상, 하, 상], ..., [우, 하, 하], [우, 하, 우], [우, 우, 상], [우, 우, 좌], [우, 우, 하], [우, 우, 우] 이다.
4. 두 번 전 연습에서 생긴 물고기의 냄새가 격자에서 사라진다.
5. 1에서 사용한 복제 마법이 완료된다. 모든 복제된 물고기는 1에서의 위치와 방향을 그대로 갖게 된다.

 

 

아이디어

시뮬레이션 문제로, 1부터 5단계를 차례로 구현한다. 격자이므로 일단 2차원 배열, 각 칸에 물고기가 여러 마리 있을 수 있으므로 배열로 생각하여 3차원 배열로 초기화한다.

1. 복제 마법 시전 : 3차원 배열이므로 deepcopy를 활용한다.
2. 물고기 이동 : 물고기의 다음 위치를 확인하여 이동할 수 있으면 이동한다. 이 때, 상어가 있는 칸, 물고기의 냄새가 있는 칸, 격자의 범위를 벗어나는 칸은 분기처리하여 이동하지 못 하도록 하고 45도 회전시킨다.
3. 상어 이동 : 무조건 3칸을 이동해야한다. 사전 순으로 나열한 것을 보면 상-좌-하-우 순으로 우선순위가 높은 것을 알 수 있다. 따라서, [상상상], [상상좌], [상상하] ... [우우우] 순으로 확인하면서, 이전에 제외시킨 물고기 수 보다 현재 제외시킨 물고기 수가 많을 때 이동 경로를 갱신한다. 단, 하나라도 경로 밖이면 제외시킨다.
   • [상상상] 일 때 2마리, [상상좌] 일 때 1마리면 갱신하지 말고 [상상상] 그대로
   • [상상상] 일 때 2마리, [상상좌] 일 때 3마리면 갱신하여 [상상좌]
   • 해당 부분 코드

     # 3. 상어 세 칸 이동
     def shark_move(s):
     
         # i, j, k 방향으로 상어가 이동할 때 잡아먹는 물고기 수
         def shark_move_ijk(r, c, i, j, k):
             fish_cnt = len(matrix[r][c])
             matrix_check = [[0]*4 for _ in range(4)]
     
             for DIR in [i, j, k]:
                 nr = r + shark_dr[DIR]
                 nc = c + shark_dc[DIR]
                 if 0 <= nr < 4 and 0 <= nc < 4:
                     # 이미 지나온 곳이면 가지 않는다.
                     if matrix_check[nr][nc]:
                         pass
                     # 처음 가는 곳이면 방문 표시 + 물고기 잡아먹기
                     else:
                         matrix_check[nr][nc] = 1
                         fish_cnt += len(matrix[nr][nc])
                         r, c = nr, nc
                 # [i, j, k] 중 하나라도 격자 범위 바깥이면 out
                 else:
                     return -1
     
             return fish_cnt
     
         # 상어의 위치
         r, c = sr, sc
         # 최종적으로 잡아먹는 물고기 수 fish_cnt, 상어 이동방향 ijk
         result_fish_cnt = 0
         result_ijk = -1
     
         # 방향 지정 => i, j, k 중 방향 하나 픽스하기
         for i in range(4):
             for j in range(4):
                 for k in range(4):
                     fish_cnt = shark_move_ijk(r, c, i, j, k)
                     # ijk가 초기값(-1)이면 무조건 한 번 갱신해준다.
                     if result_ijk == -1 and fish_cnt != -1:
                         result_ijk = (i, j, k)
                     # fish_cnt가 더 높은 ijk를 찾으면 새로 갱신
                     if result_fish_cnt < fish_cnt:
                         result_fish_cnt = fish_cnt
                         result_ijk = (i, j, k)
     
         # 최종적으로, 픽스된 ijk로 상어가 이동한다.
         for DIR in result_ijk:
             nr = r + shark_dr[DIR]
             nc = c + shark_dc[DIR]
             if matrix[nr][nc]:
                 # 해당 matrix에 물고기를 잡아먹었으므로 []
                 matrix[nr][nc] = []
                 # s번째에 냄새가 남기 때문에 fish_smell에 s를 추가
                 fish_smell[nr][nc].append(s)
             r, c = nr, nc
     
         return r, c

      

4. 냄새 삭제 : 보통 조건문을 돌면서 S번 확인하기 때문에 물고기 냄새를 기록했던 순간이 몇 번째인지 기록해두고, 그로부터 2번째 이전 냄새를 없앤다.
   • while S: 로 시작해서 s번째 냄새를 기록해두었다면, s+2번째 냄새를 삭제하면 된다.
5. 복제 마법 완료 : 1번에서 저장해둔 배열을 현재 진행하고 있는 배열에 합친다.

 

 

구현

import sys
sys.stdin = open("input.txt", "r")
from copy import deepcopy

dr = [0, -1, -1, -1, 0, 1, 1, 1]
dc = [-1, -1, 0, 1, 1, 1, 0, -1]

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


# 2. 물고기 한 칸 이동
def fish_move():

    # 물고기가 해당 방향으로 이동할 수 있는지 확인하는 함수
    def fish_can_move(nr, nc):
        # 격자의 범위를 벗어나는 칸
        if not (0 <= nr < 4 and 0 <= nc < 4):
            return False

        # 상어가 있는 칸
        if nr == sr and nc == sc:
            return False

        # 물고기의 냄새가 있는 칸
        if fish_smell[nr][nc]:
            return False

        return True

    new_matrix = [[[] for _ in range(4)] for _ in range(4)]
    for r in range(4):
        for c in range(4):
            # 기존 matrix에 있는 물고기들 확인
            while matrix[r][c]:
                d = matrix[r][c].pop()
                for i in range(8):
                    # 방향 설정
                    nd = (d - i) % 8
                    nr = r + dr[nd]
                    nc = c + dc[nd]
                    # 해당 방향으로 이동할 수 있으면 새로운 matrix에 추가
                    if fish_can_move(nr, nc):
                        new_matrix[nr][nc].append(nd)
                        break
                # 이동할 수 없으면 이동하지 않는다.
                else:
                    new_matrix[r][c].append(d)

    return new_matrix


# 3. 상어 세 칸 이동
def shark_move(s):

    # i, j, k 방향으로 상어가 이동할 때 잡아먹는 물고기 수
    def shark_move_ijk(r, c, i, j, k):
        fish_cnt = len(matrix[r][c])
        matrix_check = [[0]*4 for _ in range(4)]

        for DIR in [i, j, k]:
            nr = r + shark_dr[DIR]
            nc = c + shark_dc[DIR]
            if 0 <= nr < 4 and 0 <= nc < 4:
                # 이미 지나온 곳이면 가지 않는다.
                if matrix_check[nr][nc]:
                    pass
                # 처음 가는 곳이면 방문 표시 + 물고기 잡아먹기
                else:
                    matrix_check[nr][nc] = 1
                    fish_cnt += len(matrix[nr][nc])
                    r, c = nr, nc
            # [i, j, k] 중 하나라도 격자 범위 바깥이면 out
            else:
                return -1

        return fish_cnt

    # 상어의 위치
    r, c = sr, sc
    # 최종적으로 잡아먹는 물고기 수 fish_cnt, 상어 이동방향 ijk
    result_fish_cnt = 0
    result_ijk = -1

    # 방향 지정 => i, j, k 중 방향 하나 픽스하기
    for i in range(4):
        for j in range(4):
            for k in range(4):
                fish_cnt = shark_move_ijk(r, c, i, j, k)
                # ijk가 초기값(-1)이면 무조건 한 번 갱신해준다.
                if result_ijk == -1 and fish_cnt != -1:
                    result_ijk = (i, j, k)
                # fish_cnt가 더 높은 ijk를 찾으면 새로 갱신
                if result_fish_cnt < fish_cnt:
                    result_fish_cnt = fish_cnt
                    result_ijk = (i, j, k)

    # 최종적으로, 픽스된 ijk로 상어가 이동한다.
    for DIR in result_ijk:
        nr = r + shark_dr[DIR]
        nc = c + shark_dc[DIR]
        if matrix[nr][nc]:
            # 해당 matrix에 물고기를 잡아먹었으므로 []
            matrix[nr][nc] = []
            # s번째에 냄새가 남기 때문에 fish_smell에 s를 추가
            fish_smell[nr][nc].append(s)
        r, c = nr, nc

    return r, c


# 4. 물고기 냄새 사라짐
def fish_smell_remove(s):
    for r in range(4):
        for c in range(4):
            left_smell = []
            while fish_smell[r][c]:
                tmp = fish_smell[r][c].pop()
                # s가 아닌 것들은 left_smell에 남기기
                if tmp != s:
                    left_smell.append(tmp)
            fish_smell[r][c] = left_smell


M, S = map(int, input().split())
matrix = [[[] for _ in range(4)] for _ in range(4)]
for _ in range(M):
    fr, fc, d = map(int, input().split())
    matrix[fr-1][fc-1].append(d-1)
sr, sc = map(int, input().split())
sr -= 1; sc -= 1
fish_smell = [[[] for _ in range(4)] for _ in range(4)]

while S:
    # 1. 복제 마법 시전
    replication_matrix = deepcopy(matrix)

    # 2. 물고기 이동
    matrix = fish_move()

    # 3. 상어 이동해서 위치 변경 => 인자 S는 S번째 냄새 기록용
    sr, sc = shark_move(S)

    # 4. 물고기 냄새 사라짐 => 인자 S+2는 S+2번째 냄새 삭제용
    fish_smell_remove(S+2)

    # 5. 복제 마법 완료
    for r in range(4):
        for c in range(4):
            while replication_matrix[r][c]:
                tmp = replication_matrix[r][c].pop()
                matrix[r][c].append(tmp)
    S -= 1

# print(DataFrame(matrix))
result = 0
for r in range(4):
    for c in range(4):
        result += len(matrix[r][c])
print(result)

처음에 놓쳐서 틀렸었던 부분

• 상어가 세 칸 이동할 때, result_fish_cnt = 0, result_ijk = -1로 초기화 해두었다. 그런데, 상어가 64가지의 방향으로 이동하는 경우에서 모든 fish_cnt가 0 이면 ijk가 한 번도 갱신되지 않는다는 문제가 있었다. 이를 해결하기 위해 result_ijk = -1 로 초기값이면 격자 범위 내일때 최소한 한 번 갱신하도록 했다.