[Python/Codetree] 시공의 돌풍

https://www.codetree.ai/training-field/frequent-problems/problems/heros-of-storm/description?page=2&pageSize=20

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

문제

n * m 크기의 격자칸으로 이루어진 방 안에 먼지가 가득 쌓여있습니다. 먼지는 각 칸에 구분이 되게 쌓여있으며, 방 안의 먼지를 자동으로 치워주는 기계 시공의 돌풍을 사용해서 청소를 하고자 합니다.

시공의 돌풍은 항상 1번 열에 설치되어 있으며 크기는 두 칸을 차지합니다. 1초 동안 방에는 다음과 같은 일이 일어납니다.

1. 먼지가 인접한 4방향의 상하좌우 칸으로 확산됩니다.b. 확산되는 양은 원래 칸의 먼지의 양에 5를 나눈 값이며, 편의상 소숫점은 버립니다.d. 확산된 먼지는 방에 있는 모든 먼지가 확산을 끝낸 다음에 해당 칸에 더해지게 됩니다.
2. c. 각 칸에 확산될 때마다 원래 칸의 먼지의 양은 확산된 먼지만큼 줄어듭니다.
3. a. 인접한 방향에 시공의 돌풍이 있거나, 방의 범위를 벗어난다면 해당 방향으로는 확산이 일어나지 않습니다.
4. 시공의 돌풍이 청소를 시작합니다.b. 바람이 불면 먼지가 바람의 방향대로 모두 한 칸씩 이동합니다.
5. c. 시공의 돌풍에서 나온 바람은 먼지가 없는 청정한 바람이고 시공의 돌풍으로 들어간 먼지는 사라집니다.
6. a. 시공의 돌풍의 윗칸에서는 반시계 방향으로 바람을 일으키며, 아랫칸에서는 시계 방향으로 바람을 일으킵니다.

다음과 같이 방의 정보가 주어질 때 작동 과정을 살펴보면 다음과 같습니다.

위 그림에 표시한 파란색 점선 상자에 있는 먼지들의 확산을 살펴보면, 아래처럼 일어납니다. 범위를 벗어난 곳이나 시공의 돌풍이 있는 칸에는 확산이 되지 않습니다.

확산이 모두 끝난 뒤에 바뀐 먼지의 양은 아래와 같습니다.

이후에 시공의 돌풍이 돌풍을 일으켜 먼지를 청소합니다. 돌풍은 아래와 같은 방향으로 이루어집니다.

돌풍이 분 뒤의 방의 상태는 아래와 같습니다.

풀이

Code

from collections import deque

# 1. 먼지 확산 함수 정의
def step1() :
    # 1-1. 각 인덱스 별 가감용 리스트 생성
    summation = [[0 for _ in range(m)] for _ in range(n)]
    # 1-2.
    for x in range(n) :
        for y in range(m) :
            if graph[x][y] == -1 : continue
            # 1-2-1. 확산되는 먼지의 양 계산
            amount = graph[x][y] // 5
            # 1-2-2. 확산되는 먼지가 없다면 continue
            if not amount : continue
            # 1-2-3.
            for dir_x, dir_y in [(-1, 0), (1, 0), (0, -1), (0, 1)] :
                # 다음 위치 설정
                nx, ny = x + dir_x, y + dir_y
                # 예외 처리
                if nx < 0 or nx >= n or ny < 0 or ny >= m or graph[nx][ny] == -1 : continue
                # 다음 위치에 확산된 먼지만큼 가산
                summation[nx][ny] +=  amount
                # 현재 위치에 확산된 먼지만큼 감산
                summation[x][y] -= amount
    # 1-3.
    for x in range(n) :
        for y in range(m) :
            graph[x][y] += summation[x][y]

# 2. 청소 함수 정의
def step2() :
    # 2-1. 시공의 돌품 윗칸
    # 2-2-1. 아래행 처리
    # 해당 행의 왼쪽에 0 삽입
    graph[up].insert(1, 0)
    # 2-1-2. 오른쪽 열 처리
    for i in range(up) :
        # 현재 행의 끝에 다음 행의 끝값 제거 후 삽입
        graph[i].append(graph[i+1].pop())
    # 2-1-3. 왼쪽 열 처리
    for i in range(up - 1, -1, -1) :
        # 시공의 돌풍 윗칸일 경우 첫 값 제거
        if i == up - 1 : graph[i].popleft()
        # 이외의 경우 다음 행의 앞에 현재 행의 첫값 제거 후 삽입
        else :
            graph[i+1].appendleft(graph[i].popleft())

    # 2-2. 시공의 돌풍 아랫칸
    # 2-2-1. 윗 행 처리
    graph[down].insert(1, 0)
    # 2-2-2. 오른쪽 열 처리
    for i in range(n-2, down-1, -1) :
        # 다음 행의 끝에 현재 행의 끝값 제거 후 삽입
        graph[i+1].append(graph[i].pop())
    # 2-2-3. 왼쪽 열 처리
    for i in range(down+1, n-1) :
        # 시공의 돌풍 바로 아랫칸일 경우 첫 값 제거
        if i == down + 1 : graph[i].popleft()
        # 현재 행의 앞에 다음 행의 첫값 제거 후 삽입
        graph[i].appendleft(graph[i+1].popleft())

n, m, t = map(int, input().split())
graph = [deque(list(map(int, input().split()))) for _ in range(n)]

# 3. 시공의 돌풍 인덱스 찾기
for x in range(1, n-1) :
    if graph[x][0] == -1 :
        up, down = x, x + 1
        break
# 4.
for _ in range(t) :
    # 3-1. 먼지 확산
    step1()
    # 3-2. 청소
    step2()
# 5. 결과 출력
ans = 0
for x in range(n) :
    for y in range(m) :
        if graph[x][y] == -1 : continue
        ans += graph[x][y]
print(ans)