[알고리즘 문제] 공기 청정기 (Python / 파이썬)

문제

알고리즘잡스 강의실의 쾌적한 공기 상태를 보장하기 위해 공기청정기를 설치했다. 어느날, 공기청정기가 제대로 동작하는지 궁금해진 영진은 현재 강의실의 공기상태를 알아내는 프로그램을 만들었다. 편의상 강의실 내부는 격자판으로 그려지고, 각 칸에는 공기의 나쁨 정도를 숫자로 표현하도록 제작되었다.

[그림 1]

해당 프로그램에서 공기의 확산 특징은 다음과 같다.
 - 공기는 현재 위치에서 상하좌우로 확산된다. 만약 확산할 좌표가 존재하지 않거나, 공기청정기 위치일 경우 해당 위치로는 퍼지지 않는다.
 - 공기의 나쁨 정도가 5보다 작을 경우 확산이 일어나지 않는다.
 - 공기의 확산이 일어났을때, 퍼지는 나쁨 정도는 기준 위치에서 5로 나눈 몫이다.
 - 확산을 일으킨 후의 기준 위치의 공기의 나쁨 정도는 (현재 공기의 나쁨 정도) - (퍼진 공기의 나쁨 정도)*(확산된 칸의 수)이다.
 - 하나의 칸에 두 공기가 확산되어 왔을 경우, 확산된 나쁨 정도를 합한다.
 - 공기는 1초에 한 번씩 확산이 된다.

[그림 2]

공기청정기의 동작 방식 및 특징은 다음과 같다.
 - 공기청정기는 항상 강의실 오른쪽 벽면에 설치되어있고, 그 크기는 격자판 기준 가로 1칸, 세로 2칸을 차지한다.
 - 공기청정기는 총 2곳에서 바람을 내뿜고 있는데, 세로 칸 중 윗 칸에서는 시계 방향으로 공기를 순환시키는 바람이 나오고, 아랫칸에서는 반시계 방향으로 바람이 나온다.
 - 바람에 의해 공기가 이동하며, 격자판 기준 1초당 이동하는 칸 수는 1칸이다.
 - 바람의 시작점은 공기청정기의 위치이며, 바람은 벽면을 타고 이동한다.
 - 공기가 바람을 타고 공기청정기의 위치에 도착할 경우, 정화되어 다시 바람을 타고 나오게 된다. 이때, 정화된 공기의 나쁨 정도는 0이다.

[그림 3]

강의실 정보가 주어졌을때, S초가 지난 후 공기의 나쁨 정도를 모두 합한 값을 알아내보자. 공기청정기는 항상 공기가 확산된 후에 동작한다.예를 들어, [그림 1]의 상황에서 1초가 지난 모습은 다음과 같다.

[그림 4] 공기가 확산되고, 공기청정기에 의해 순환되는 모습

입력

첫 번째 줄에 테스트 케이스의 개수 T가 주어진다. 다음 줄부터 T개의 테스트 케이스에 대한 정보가 주어진다. 각각의 테스트 케이스의 첫 번째 줄에 강의실 크기 R, C 와 시간 S 가 공백을 통해 구분하여 주어진다. 두 번째 줄부터 R 개의 줄에 걸쳐 강의실 공기 정보가 주어진다. 각 줄에는 C 개의 숫자가 공백을 통해 구분하여 주어지며, 각 숫자는 -1 이상 1000 이하의 정수이다. -1은 공기청정기를 뜻하며 세로로 인접하게 2개 주어진다. 또한, 첫번째 행과 마지막 행에 -1이 존재할 수 없다. (5 ≤ R, C ≤ 100, 1 ≤ S ≤ 1000)

출력

각 테스트 케이스에 대해 S초가 지난 후 공기의 나쁨 정도를 모두 합한 값을 출력한다. 각 테스트 케이스의 출력 양식은 "#t r"이다. t는 테스트 케이스의 번호이며, 1부터 시작한다. r은 문제에 대한 결과값을 뜻한다.

---

문제 풀이 

공기 청정기 문제는 동시에 확산이 일어난다는 점, 그리고 테두리의 원소들만 

시계방향 혹은 반시계방향으로 회전한다는 점에 있어서 구현이 까다로웠다. 

 

전체적인 문제의 단계는 나쁜 공기가 1초마다 확산 -> 공기 청정기가 청소 이다. 

1. 5 이상의 공기만 확산된다. 

2. 상하좌우로 확산된다. (범위 내에서만, 공기청정기 위치는 확산 안됨)

- 확산되는 기준 위치는 확산되는 만큼 빼줘야 한다. 

3. 공기가 확산될 때 하나씩 수행하면 올바르게 확산되지 않는다. 

- 동시에 확산되도록 임시 배열을 만들어줘야 한다. 

4. 공기청정기 위치를 기준으로 시계방향 혹은 반시계 방향으로 공기가 순환된다. 

- 공기청정기 위치를 기준으로 순환되기 때문에 공기청정기 위치를 알아둬야 한다.

- 공기청정기는 항상 오른쪽 끝에 위치하므로 행의 위치만 알면 된다. 

- 시계방향 혹은 반시계방향으로 하나씩 이동하면 원본이 훼손된다. 따라서 임시 배열을 만들어야 한다.

5. 모든 과정이 끝난 뒤 남은 공기의 총합을 구해준다. 

 

위 과정을 따라 구현하면 답을 구할 수 있다. 

---

My Code

# 상하좌우로 탐색할 방향변수
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# 공기를 확산시키는 함수
def spread():
    temp = [[0] * m for _ in range(n)]

    # 동시에 확산시키기 위해 임시배열에 원본 복사 
    for i in range(n):
        for j in range(m):
            temp[i][j] = array[i][j]

    for i in range(n):
        for j in range(m):
            if temp[i][j] >= 5: # 5 이상인 것만 확산
                for k in range(4): # 상하좌우로 확산
                    nx = i + dx[k]
                    ny = j + dy[k]
                    # 범위 내이고 공기청정기 위치가 아니라면
                    if 0 <= nx < n and 0 <= ny < m and temp[nx][ny] != -1:
                        array[nx][ny] += temp[i][j] // 5 # 다음 위치에 5로 나눈 몫을 더해줌
                        array[i][j] -= temp[i][j] // 5   # 내 위치엔 확산 시킨 만큼 빼줌 

# 공기청정기가 공기를 순환하는 함수 
def clean():
    temp = [[0] * m for _ in range(n)]

    # 시계방향/반시계방향으로 동시에 회전되도록 임시 배열에 원본 복사 
    for i in range(n):
        for j in range(m):
            temp[i][j] = array[i][j] 

    # 공기청정기의 윗 부분은 시계 방향으로 회전 
    for j in range(m - 2):
        array[up][j] = temp[up][j + 1]
    for i in range(up):
        array[i][0] = temp[i + 1][0]
    for j in range(1, m):
        array[0][j] = temp[0][j - 1]
    for i in range(1, up):
        array[i][m - 1] = temp[i - 1][m - 1]
    array[up][m - 2] = 0 

    # 공기청정기의 아래부분은 반시계 방향으로 회전
    for j in range(m - 2):
        array[down][j] = temp[down][j + 1]
    for i in range(down + 1, n):
        array[i][0] = temp[i - 1][0]
    for j in range(1, m):
        array[n - 1][j] = temp[n - 1][j - 1]
    for i in range(down + 1, n - 1):
        array[i][m - 1] = temp[i + 1][m - 1]
    array[down][m - 2] = 0 

for tc in range(int(input())):
    n, m, s = map(int,input().split()) # 강의실의 세로, 가로, 시간

    array = []
    up = down = -1 # 공기청정기의 행 위치를 저장할 변수 
    for i in range(n):
        array.append(list(map(int,input().split()))) # 공기 정보
        for j in range(m):
            if array[i][j] == -1:   # 공기청정기의 위치라면
                if up == -1: up = i # 행의 위치를 저장
                else: down = i      # up에 이미 저장됐다면 down에 행의 위치 저장

    for _ in range(s): # s초 동안
        spread()  # 공기 확산
        clean()   # 공기 순환
    
    # 확산 순환이 모두 종료되면 남은 공기의 값을 모두 더해줌
    sum_value = 0
    for i in range(n):
        for j in range(m):
            if array[i][j] != -1:
                sum_value += array[i][j]

    print('#' + str(tc + 1), end = ' ')
    print(sum_value)