백준 23290 | 마법사 상어와 복제 - python

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

23290번: 마법사 상어와 복제

문제

마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기, 블리자드 마법을 할 수 있다. 오늘은 기존에 배운 물복사버그 마법의 상위 마법인 복제를 배웠고, 4 × 4 크기의 격자에서 연습하려고 한다. (r, c)는 격자의 r행 c열을 의미한다. 격자의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (4, 4)이다.

격자에는 물고기 M마리가 있다. 각 물고기는 격자의 칸 하나에 들어가 있으며, 이동 방향을 가지고 있다. 이동 방향은 8가지 방향(상하좌우, 대각선) 중 하나이다. 마법사 상어도 연습을 위해 격자에 들어가있다. 상어도 격자의 한 칸에 들어가있다. 둘 이상의 물고기가 같은 칸에 있을 수도 있으며, 마법사 상어와 물고기가 같은 칸에 있을 수도 있다.

상어의 마법 연습 한 번은 다음과 같은 작업이 순차적으로 이루어진다.

1. 상어가 모든 물고기에게 복제 마법을 시전한다. 복제 마법은 시간이 조금 걸리기 때문에, 아래 5번에서 물고기가 복제되어 칸에 나타난다.
2. 모든 물고기가 한 칸 이동한다. 상어가 있는 칸, 물고기의 냄새가 있는 칸, 격자의 범위를 벗어나는 칸으로는 이동할 수 없다. 각 물고기는 자신이 가지고 있는 이동 방향이 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전시킨다. 만약, 이동할 수 있는 칸이 없으면 이동을 하지 않는다. 그 외의 경우에는 그 칸으로 이동을 한다. 물고기의 냄새는 아래 3에서 설명한다.
3. 상어가 연속해서 3칸 이동한다. 상어는 현재 칸에서 상하좌우로 인접한 칸으로 이동할 수 있다. 연속해서 이동하는 칸 중에 격자의 범위를 벗어나는 칸이 있으면, 그 방법은 불가능한 이동 방법이다. 연속해서 이동하는 중에 상어가 물고기가 있는 같은 칸으로 이동하게 된다면, 그 칸에 있는 모든 물고기는 격자에서 제외되며, 제외되는 모든 물고기는 물고기 냄새를 남긴다. 가능한 이동 방법 중에서 제외되는 물고기의 수가 가장 많은 방법으로 이동하며, 그러한 방법이 여러가지인 경우 사전 순으로 가장 앞서는 방법을 이용한다. 사전 순에 대한 문제의 하단 노트에 있다.
4. 두 번 전 연습에서 생긴 물고기의 냄새가 격자에서 사라진다.
5. 1에서 사용한 복제 마법이 완료된다. 모든 복제된 물고기는 1에서의 위치와 방향을 그대로 갖게 된다.

격자에 있는 물고기의 위치, 방향 정보와 상어의 위치, 그리고 연습 횟수 S가 주어진다. S번 연습을 모두 마쳤을때, 격자에 있는 물고기의 수를 구해보자.

입력

첫째 줄에 물고기의 수 M, 상어가 마법을 연습한 횟수 S가 주어진다. 둘째 줄부터 M개의 줄에는 물고기의 정보 fx, fy, d가 주어진다. (fx, fy)는 물고기의 위치를 의미하고, d는 방향을 의미한다. 방향은 8 이하의 자연수로 표현하고, 1부터 순서대로 ←, ↖, ↑, ↗, →, ↘, ↓, ↙ 이다. 마지막 줄에는 sx, sy가 주어지며, 상어가 (sx, sy)에 있음을 의미한다.

격자 위에 있는 물고기의 수가 항상 1,000,000 이하인 입력만 주어진다.

출력

S번의 연습을 마친 후 격자에 있는 물고기의 수를 출력한다.

제한

• 1 ≤ M ≤ 10
• 1 ≤ S ≤ 100
• 1 ≤ fx, fy, sx, sy ≤ 4
• 1 ≤ d ≤ 8
• 두 물고기 또는 물고기와 상어가 같은 칸에 있을 수도 있다.

 

이 문제의 경우, 복제 작업을 천천히 따라가면서 코드를 작성하는 것이 무엇보다 중요하다고 생각했다.

그래서 각 과정을 종이에 써보면서 문제를 풀어나갔고

이후에 코드를 작성했다.

 

첫번째로는 물고기들이 복제가 되는 과정이다.

문제를 읽어보면 복제된 물로기에 대해서만 상어가 잡아먹기 때문에 새로운 리스트를 만들어서 거기에 복제된 물고기를 저장해야한다.

 

fishes에 저장된 현재 존재하는 물고기의 리스트를 돌면서 복제된 물고기를 copy_fishes에 저장하고

bowls에 표시를 한다.

 

물고기들이 이동할 때 상어가 있는 자리, 죽은 물고기의 냄새가 남아있는 자리, 범위 내에만 존재해야되기 때문에

해당 조건을 달아준다.

# 물고기 복제
copy_fishes = []
for y, x, d in fishes:
    for i in range(8):
        nj, ni = y + dr[(d - i) % 8], x + dc[(d - i) % 8]
        if 0 <= nj < 4 and 0 <= ni < 4 and not smells[nj][ni] and (nj != sy or ni != sx):
            copy_fishes.append([nj, ni, (d - i) % 8])
            break
    else:
        copy_fishes.append([y, x, d])

# 위치 별 복제된 물고기의 수 저장할 리스트
bowls = [[0 for _ in range(4)] for _ in range(4)]
for y, x, _ in copy_fishes:
    bowls[y][x] += 1

 

 

그 다음 상어가 3칸씩 움직이면서 물고기를 잡아먹는데, 상하좌우로 움직일 수 있기 때문에

DFS를 통해 각 움직임에서 잡아먹은 물고기수, 마지막 상어의 위치를 저장한다.

# 상어 이동 dfs
def SharkShock(i, row, col, copies, bowls, c, route, directions):
    global routes
    # 3번의 움직임이 완료되면 routes에 루트, 이동 방향, 먹은 물고기 수 저장
    if i == 3:
        routes.append([route, directions, c])
    else:
        # 4방향으로 회전하며 이동
        for idx in range(4):
            nj, ni = row + s_dr[idx], col + s_dc[idx]
            if 0 <= nj < 4 and 0 <= ni < 4:
                # 한 번 방문한 곳은 물고기를 잡지 않고, 처음 방문한 곳은 물고기 수만틈 잡아먹는다.
                if not visited[nj][ni]:
                    visited[nj][ni] = True
                    SharkShock(i + 1, nj, ni, copies, bowls, c + bowls[nj][ni], route + [[nj, ni]], directions + [idx])
                    visited[nj][ni] = False
                else:
                    SharkShock(i + 1, nj, ni, copies, bowls, c, route + [[nj, ni]], directions + [idx])

# 상어의 이동 경로와 잡은 물고기 수 저장할 리스트
routes = []
visited = [[False for _ in range(4)] for _ in range(4)]
SharkShock(0, sy, sx, copy_fishes, bowls, 0, [], [])

# 잡아먹은 물고기 수, 이동방향에 대한 우선순위 순으로 정렬 후 가장 앞서 있는 값만 저장
routes = sorted(routes, key=lambda x: (-x[2], x[1]))[0]

 

여기서 중요한 것이 잡아먹은 물고기 수가 같을 때 상어를 선정하는 과정에서 마지막 상어의 위치를 정려하는 것이 아니라 ←, ↖, ↑, ↗, →, ↘, ↓, ↙ 와 같은 순서로 상어를 선정해야하는 것이 핵심이었다.

 

문제의 해당 내용을 이해하는데 시간이 걸려 풀이를 완료하는데 시간이 걸렸다.

 

이제는 선정된 상어의 위치와 경로를 담은 리스트를 활용하여 상어의 경로에 있는 "복제된 물고기를" 게저하는 과정을 거쳐야한다.

잡아먹힌 물고기가 있는 위치를

smells 리스트에 -3을 저장하여 죽은 물고기의 냄새를 표시해준다.

# 잡아먹은 물고기 수, 이동방향에 대한 우선순위 순으로 정렬 후 가장 앞서 있는 값만 저장
routes = sorted(routes, key=lambda x: (-x[2], x[1]))[0]

# 복제된 물고기가 상어의 이동경로에 있으면 smell을 업데이트하고, 없으면 존재하는 물고기 리스트에 추가
while copy_fishes:
    row, col, direction = copy_fishes.pop()
    if [row, col] not in routes[0]:
        fishes.append([row, col, direction])
    else:
        smells[row][col] = -3

 

마지막으로 시간이 지남에 따라 냄새가 사라지는 과정을 해줘야하는데

smells 리스트를 돌면서 마이너스 값을 가지는 친구들을 +1해준다.

다 완수한 뒤에는 상어의 위치를 업데이트 해준다.

# 남아있는 냄새가 있는 구역의 값을 +1
for row in range(4):
    for col in range(4):
        # 냄새가 남아있는 지역에 +1 을 해준다
        if smells[row][col] < 0:
            smells[row][col] += 1

# 상어 위치 업데이트
sy, sx = routes[0][-1]

 

이 하나의 사이클을 주어진 횟수만큼 수행을 하면 된다.

 

전체 코드를 보자

import sys

input = sys.stdin.readline

# 물고기 이동 방향
dr = [0, -1, -1, -1, 0, 1, 1, 1]
dc = [-1, -1, 0, 1, 1, 1, 0, -1]

# 상어 이동방향
s_dr = [-1, 0, 1, 0]
s_dc = [0, -1, 0, 1]


# 상어 이동 dfs
def SharkShock(i, row, col, copies, bowls, c, route, directions):
    global routes
    # 3번의 움직임이 완료되면 routes에 루트, 이동 방향, 먹은 물고기 수 저장
    if i == 3:
        routes.append([route, directions, c])
    else:
        # 4방향으로 회전하며 이동
        for idx in range(4):
            nj, ni = row + s_dr[idx], col + s_dc[idx]
            if 0 <= nj < 4 and 0 <= ni < 4:
                # 한 번 방문한 곳은 물고기를 잡지 않고, 처음 방문한 곳은 물고기 수만틈 잡아먹는다.
                if not visited[nj][ni]:
                    visited[nj][ni] = True
                    SharkShock(i + 1, nj, ni, copies, bowls, c + bowls[nj][ni], route + [[nj, ni]], directions + [idx])
                    visited[nj][ni] = False
                else:
                    SharkShock(i + 1, nj, ni, copies, bowls, c, route + [[nj, ni]], directions + [idx])


# 여기서부터 시작
answer = 0
m, s = map(int, input().split())
# 존재하는 물고기의 [위치, 바라보는 방향] 저장
fishes = []
# 잡힌 물고기의 냄새를 저장할 공간
smells = [[0 for _ in range(4)] for _ in range(4)]

# 물고기 저장
for _ in range(m):
    fy, fx, d = map(int, input().split())
    fishes.append([fy - 1, fx - 1, d - 1])

# 상어 위치 저장
sy, sx = map(int, input().split())
sy, sx = sy - 1, sx - 1

for _ in range(s):
    # 물고기 복제
    copy_fishes = []
    for y, x, d in fishes:
        for i in range(8):
            nj, ni = y + dr[(d - i) % 8], x + dc[(d - i) % 8]
            if 0 <= nj < 4 and 0 <= ni < 4 and not smells[nj][ni] and (nj != sy or ni != sx):
                copy_fishes.append([nj, ni, (d - i) % 8])
                break
        else:
            copy_fishes.append([y, x, d])

    # 위치 별 복제된 물고기의 수 저장할 리스트
    bowls = [[0 for _ in range(4)] for _ in range(4)]
    for y, x, _ in copy_fishes:
        bowls[y][x] += 1

    # 상어의 이동 경로와 잡은 물고기 수 저장할 리스트
    routes = []
    visited = [[False for _ in range(4)] for _ in range(4)]
    SharkShock(0, sy, sx, copy_fishes, bowls, 0, [], [])

    # 잡아먹은 물고기 수, 이동방향에 대한 우선순위 순으로 정렬 후 가장 앞서 있는 값만 저장
    routes = sorted(routes, key=lambda x: (-x[2], x[1]))[0]

    # 복제된 물고기가 상어의 이동경로에 있으면 smell을 업데이트하고, 없으면 존재하는 물고기 리스트에 추가
    while copy_fishes:
        row, col, direction = copy_fishes.pop()
        if [row, col] not in routes[0]:
            fishes.append([row, col, direction])
        else:
            smells[row][col] = -3

    # 남아있는 냄새가 있는 구역의 값을 +1
    for row in range(4):
        for col in range(4):
            # 냄새가 남아있는 지역에 +1 을 해준다
            if smells[row][col] < 0:
                smells[row][col] += 1

    # 상어 위치 업데이트
    sy, sx = routes[0][-1]

print(len(fishes))

 

해당 게시글이 도움이 되었다면,