(Python/파이썬) - 백준(BOJ) 17144번 : 미세먼지 안녕!

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

17144번: 미세먼지 안녕!

---

• 문제 : 

미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다.

공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r, c)에 있는 미세먼지의 양은 A(r,c)이다.

1초 동안 아래 적힌 일이 순서대로 일어난다.

 

1. 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.
   • (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
   • 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
   • 확산되는 양은 A(r,c)/5이고 소수점은 버린다.
   • (r, c)에 남은 미세먼지의 양은 A(r,c) - (A(r,c)/5)×(확산된 방향의 개수) 이다.

 

1. 공기청정기가 작동한다.
   • 공기청정기에서는 바람이 나온다.
   • 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
   • 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.
   • 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.

 

 

다음은 확산의 예시이다.

1. 왼쪽과 오른쪽에 칸이 없기 때문에, 두 방향으로만 확산이 일어났다.

 

 

2. 인접한 네 방향으로 모두 확산이 일어난다.

 

3.  공기청정기가 있는 칸으로는 확산이 일어나지 않는다.

 

 

 

공기청정기의 바람은 다음과 같은 방향으로 순환한다.

방의 정보가 주어졌을 때, T초가 지난 후 구사과의 방에 남아있는 미세먼지의 양을 구해보자.

 

 

 

---

• 풀이 :

구현 문제였습니다.

백준 골드 4짜리 문제인데 이정도 수준이면 코딩테스트 2번 정도에 출제될만할 것 같습니다.

 

구현문제는 어떤 복잡한 알고리즘의 흐름보다는 예외케이스를 포함하여 동작하고 가독성과 효율성 좋게 짜는 노하우가 필요하다고 생각합니다.

 

최대한 깔끔하게 짜보았습니다.

 

핵심 아이디어를 간단하게 설명하자면

 

1. 미세먼지가 4방면으로 퍼지는 조건 ( 0부터 R 또는 C 까지의 범위 안에 들어가는지, 공기청정기가 없는지) 을 잘 따져야 합니다. 또한 tmp 배열을 만들어 변화한 값을 저장한 후 한번에 더해주는 형태로 진행해야 합니다. 이전의 변화값이 다음 진행에 영향을 줄 수 있기 때문입니다.

 

2. 2차원 배열에서 회전을 구현하기 어려워하는 사람들이 많습니다. 제가 가장 좋아하는 아이디어는 dx,dy를 상좌우하의 시계방향으로 선언한 뒤 d를 1씩 더하거나 빼서 시계, 반시계방향으로 이동하는 방법입니다. 

 

나머지는 주석에 달아 놓았으니 헷갈리는 부분은 참고하면 될 것 같습니다.

 

 

 

---

• 소스코드 : 

import sys
input = sys.stdin.readline

R,C,T = map(int,input().split())
board = [list(map(int,input().split())) for _ in range(R)]
robot_top = 0
robot_bottom = 0

#상 우 하 좌
dx = [-1,0,1,0]
dy = [0,1,0,-1]

def spread():  # 1초마다 미세먼지가 퍼지는 동작
    
    change = [[0] * C for _ in range(R)]
    for x in range(R):
        for y in range(C):
            if board[x][y] > 0: # 미세먼지가 있는 경우
                tmp = 0
                for i in range(4):  # 4방면으로 퍼짐
                    ax = x + dx[i]
                    ay = y + dy[i]
                    if 0 <= ax < R and 0 <= ay < C:  # board 에서 벗어나지 않는 범위일 경우만
                        if board[ax][ay] != -1:  # 공기청정기가 아닌 위치만 확산
                            change[ax][ay] += board[x][y]//5
                            tmp += board[x][y]//5
                board[x][y] -= tmp
    for x in range(R):
        for y in range(C):
            board[x][y] += change[x][y]

def rotation():
    def top_rotate(): # 위쪽 회전
        d = 1 # 오른쪽 방향으로 시작
        before = 0
        x, y = robot_top, 1 # 공기청정기 머리부분의 바로 오른쪽 칸부터 시작
        while True:
            ax = x + dx[d]
            ay = y + dy[d]
            if ax == R or ay == C or ax == -1 or ay == -1: # 현재 좌표가 꼭짓점인 경우
                d = (d-1)%4
                continue
            if x == robot_top and y == 0: # 한 바퀴 회전 완료해서 공기청정기 좌표로 다시 돌아온 경우
                break
            board[x][y], before  = before, board[x][y]
            x, y = ax, ay


    def bottom_rotate():  # 아래 회전
        d = 1 # 오른쪽 방향으로 시작
        before = 0
        x, y = robot_bottom, 1 # 공기청정기 아래부분의 바로 오른쪽 칸부터 시작
        while True:
            ax = x + dx[d]
            ay = y + dy[d]
            if ax == R or ay == C or ax == -1 or ay == -1: # 현재 좌표가 꼭짓점인 경우
                d = (d+1)%4
                continue
            if x == robot_bottom and y == 0: # 한 바퀴 회전 완료해서 공기청정기 좌표로 다시 돌아온 경우
                break
            board[x][y], before  = before, board[x][y]
            x, y = ax, ay
            
    top_rotate()
    bottom_rotate()


for i in range(R): # 공기청정기의 위치를 찾기 위함
    if board[i][0] == -1:
        robot_top = i
        robot_bottom = i+1
        break

for _ in range(T): # T만큼 수행
    spread() 
    rotation() 
    
answer = 2  #공기청정기 2칸 -1인 것 상쇄하기 위함
for i in range(R):
    answer += sum(board[i])
print(answer)