[백준/파이썬] 17144번 미세먼지 안녕!

solved.ac Class 4레벨에 속한 문제이다.

문제 주소: https://www.acmicpc.net/problem/17144

17144번: 미세먼지 안녕!

문제 해석

확산과 공기청정기를 순서대로 작동하면 된다.

1. 확산은 미세먼지가 존재하는 위치에 상하좌우로 5를 나눈 소수점을 제거한 값만큼 확산된다.
   이때 확산할 공간이 없거나 확산 위치에 공기청정기가 존재한다면 확산할 수 없다.
   확산이 되는 만큼 감소된다. (확산에서 미세먼지는 항상 보존된다.)
   미세먼지의 양이 5미만이라면 확산되지 않는다는 점을 생각해서 구현해야 한다.
2. 공기청정기는 항상 1열에 존재하며, 2칸을 차지한다.
   그림처럼 1칸씩 순환하며, 순환된 미세먼지가 공기청정기에 닿았을 경우 미세먼지가 사라진다.

문제 풀이

먼저 공기청정기의 위, 아래칸의 좌표를 저장해 주었다.

 

확산은 r, c 크기의 새 리스트에 갱신한 뒤, 복사해 주는 방식으로 구현했다.

모든 maps을 돌며 미세먼지가 존재한다면 상하좌우에 확산 가능한지 확인해 주었다. (벽이거나, 공기청정기가 존재한다면 확산 X)

이후 확산된 부분은 5를 나눈 값만큼 더해주고, 확산이 시작된 부분은 해당 값만큼 빼주었다.

모든 확산은 한꺼번에 일어나기 때문에 새 배열에 값을 갱신해 나가는 것이 포인트이다.

 

공기청정은 위와 아래 좌표를 나누어 구현해 주었다.

항상 1열에 존재하기 때문에 같은 방향으로 공기청정된다.

즉, 위쪽 공기청정기는 우 -> 상 -> 좌 -> 하 방향으로 청정되며, 청정기의 위치에 도달한 미세먼지는 사라진다.

마찬가지로 아래 공기청정기는 우 -> 하 -> 좌 -> 상 방향으로 청정시켜 구현하면 된다.

 

마지막 결괏값은 maps의 모든 값을 더해주는데, 공기청정기가 존재하는 -1을 제외하는 것을 유의해주면 결괏값을 도출하면 된다.

문제 코드

dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
def solve(r, c, t, maps):
    # 공기 청정기 좌표 저장
    fresher = []
    for i in range(r):
        if maps[i][0] == -1: fresher.append((i, 0))
    
    def difussion():
        # 확산
        nonlocal maps
        scores = [[0] * c for _ in range(r)]
        for i in range(r):
            for j in range(c):
                if maps[i][j] > 0:
                    temp = maps[i][j]
                    for dir in range(4):
                        x, y = i + dx[dir], j + dy[dir]
                        if not(0 <= x < r and 0 <= y < c): continue
                        if maps[x][y] == -1: continue
                        scores[x][y] += maps[i][j] // 5
                        temp -= maps[i][j] // 5
                    scores[i][j] += temp
    
        maps = scores.copy()
        for x, y in fresher:
            maps[x][y] = -1
        return
    
    def freshing():
        nonlocal maps
        # 위쪽 공기청정기 순환
        i, j = fresher[0]
        temp = 0
        while 0 <= j + 1 < c:
            temp, maps[i][j + 1] = maps[i][j + 1], temp
            j += 1
        while 0 <= i - 1 < r:
            temp, maps[i - 1][j] = maps[i - 1][j], temp
            i -= 1
        while 0 <= j - 1 < c:
            temp, maps[i][j - 1] = maps[i][j - 1], temp
            j -= 1
        while 0 <= i + 1 < r and maps[i + 1][j] != -1:
            temp, maps[i + 1][j] = maps[i + 1][j], temp
            i += 1
        # 아래 공기청정기 순환
        i, j = fresher[1]
        temp = 0
        while 0 <= j + 1 < c:
            temp, maps[i][j + 1] = maps[i][j + 1], temp
            j += 1
        while 0 <= i + 1 < r:
            temp, maps[i + 1][j] = maps[i + 1][j], temp
            i += 1
        while 0 <= j - 1 < c:
            temp, maps[i][j - 1] = maps[i][j - 1], temp
            j -= 1
        while 0 <= i - 1 < r and maps[i - 1][j] != -1:
            temp, maps[i - 1][j] = maps[i - 1][j], temp
            i -= 1
    
    def result():
        answer = 0
        for i in range(r):
            for j in range(c):
                if maps[i][j] > 0:
                    answer += maps[i][j]
        return answer
                    
    for _ in range(t):
        difussion()
        freshing()
    return result()

r, c, t = map(int, input().split())
maps = [list(map(int, input().split())) for _ in range(r)]
print(solve(r, c, t, maps))

제출 결과

구현만 차근차근 잘한다면 어렵지 않은...
하지만 구현이 빡세다..