[BOJ] 17144. 미세먼지 안녕! (🥇, 구현/시뮬레이션)

lemythe423·2023년 5월 13일

BOJ 문제풀이

목록 보기

25/133

문제

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

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

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

미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.

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

공기청정기가 작동한다.

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

다음은 확산의 예시이다.

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

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

입력
첫째 줄에 R, C, T (6 ≤ R, C ≤ 50, 1 ≤ T ≤ 1,000) 가 주어진다.

둘째 줄부터 R개의 줄에 Ar,c (-1 ≤ Ar,c ≤ 1,000)가 주어진다. 공기청정기가 설치된 곳은 Ar,c가 -1이고, 나머지 값은 미세먼지의 양이다. -1은 2번 위아래로 붙어져 있고, 가장 윗 행, 아랫 행과 두 칸이상 떨어져 있다.

출력
첫째 줄에 T초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다.

풀이

구현 순서

미세먼지가 먼저 확산한다(diffusion)

위쪽은 반시계방향, 아래쪽은 시계방향으로 회전한다(rotate)

두 가지를 순서대로 구현하면 되는 구현문제다

구현

확산

기본적으로 4방향으로 확산할 수 있지만 없는 칸이거나 공기청정기가 있는 칸인 경우 예외처리
(현재 칸의 미세먼지 양) // 5 만큼 확산됨
위에서 구한 값과 확산될 수 있는 칸의 수만큼을 현재 칸의 미세먼지 양에서 빼줘야 함
위에서 아래, 왼쪽으로 오른쪽으로 차례대로 탐색하며 한 칸씩 확산시키기 때문에 기존의 배열 값을 건드리지 않고(기존의 미세먼지 값을 알아야 하니까) 새로운 배열에 값을 넣은 다음에 그 값을 다시 기존 배열에 넣는 방식이 좋을 듯

풀이1

미세먼지가 있는 칸을 먼저 구한 다음에 그 칸에 대해서만 확산을 시키면 조금 더 빠를 거라고 생각했는데, 30번쯤 회전하고 나면 미세먼지가 없는 칸이 없기 때문에 오히려 비효율적
확산될 양이 (5로 나눈 몫) 0인 경우에 대해서는 값을 안 구하는 조건문을 넣었는데 이것도 오히려 더 비효율적인듯?
전형적인 그래프 탐색 방식을 그대로 가져왔는데 빡구현은 오히려 이런 방식이 시간이 더 오래 걸리는 것 같다

def speard_dust(dusts, R, C, dust_lst, new_dusts):
    dust_lst = FIND_DUST(dusts, R, C)

    for dust, amount in dust_lst.items():
        r, c = dust
        to_amount = amount // 5
        if to_amount > 0:
            for d in range(4):
                dr, dc = SPREAD_DIR[d]
                nr, nc = r+dr, c+dc
                if -1 < nr < R and -1 < nc < C and dusts[nr][nc] != -1: 
                    new_dusts[nr][nc] += to_amount
                    amount -= to_amount
            
        new_dusts[r][c] += amount

    return new_dusts

풀이2

4방향에 대해서 각각 접근해서 찾는 방식으로 구했고, 따로 미세먼지가 있는 칸을 구하진 않고 배열의 처음부터 끝까지 전부다 탐색했다
단, 공기 청정기가 있는 경우는 제외했고 확산될 양(diffusion_dust)에 대해서는 0이 되어도 그냥 계산을 진행했다. 조건문을 넣는 게 굳이 안 해도 될 조건 검사를 하는 느낌?
풀이1에서는 기존의 dust에 확산 한 번 될 때마다 그 값을 빼주는 식으로 했는데 실제로는 기존의 dust - dust//5 * (확산된 방향의 수) 이기 때문에 문제에서 말하는 방식 그대로 구현했다
if~elif 문으로 구현하는 바람에 처음에는 제대로 안 구해짐ㅜ

def diffusion(dusts, R, C):
    new_dusts = [[0] * C for _ in range(R)]
    for i in range(R):
        for j in range(C):
            # 공기청정기 피하기
            if dusts[i][j] == -1:
                new_dusts[i][j] = -1
                continue

            # 굳이 미세먼지가 없는 부분은 확인하지 않음 왜냐면 많이 반복될수록 미세먼지 없는 칸이 없으므로..
            dust = dusts[i][j]
            diffusion_dust, diffusion_area = dust // 5, 0
            if i+1 < R and dusts[i+1][j] != -1:
                new_dusts[i+1][j] += diffusion_dust
                diffusion_area += 1
            if j+1 < C and dusts[i][j+1] != -1:
                new_dusts[i][j+1] += diffusion_dust
                diffusion_area += 1
            if i-1 > -1 and dusts[i-1][j] != -1:
                new_dusts[i-1][j] += diffusion_dust
                diffusion_area += 1
            if j-1 > -1 and dusts[i][j-1] != -1:
                new_dusts[i][j-1] += diffusion_dust
                diffusion_area += 1
            new_dusts[i][j] += (dust - diffusion_dust * diffusion_area)
    
    return new_dusts

미세먼지 청소(회전)

배열 돌리기1 와 비슷한 문제같은데 오히려 더 쉬운 버전같다
문제에서 공기청정기 쪽으로 빨려들어간 미세먼지는 없어진다고 했으므로 배열을 돌릴 때 이 부분의 값은 없애주면 된다. 반대로, 공기청정기의 경우 그 위치에 그대로 있어야 하기 때문에 이 부분의 값도 회전할 때 제외하면 된다

풀이1

배열 돌리기 풀이 방식 그대로 풀었다. 시계 방향으로 돌 때는 반시계방향으로, 반시계 방향일 때는 시계 방향으로 한칸씩 움직이면서 값을 서로 바꿔주면 된다.
이 방식이 비효율적인 이유는 1. 굳이 값을 '바꿔줘야함' 2. 공기청정기에 흡수될 미세먼지의 칸이 있기 때문에 이 칸 때문에 값을 바꿔줄 필요 없이 한칸씩 땡기면 됨
공기청정기에 흡수되는 값의 칸은 0으로 바꿔주는 처리를 해야 함

# TOP_CLEAN
    START_ROW, START_COL = TOP_BOUNDARY, 0
    for d in range(4):
        dr, dc = TOP_CLEAN[d]
        while -1 < START_ROW+dr <= TOP_BOUNDARY and -1 < START_COL+dc < C:
            dusts[START_ROW][START_COL], dusts[START_ROW+dr][START_COL+dc] = dusts[START_ROW+dr][START_COL+dc], dusts[START_ROW][START_COL]
            START_ROW += dr
            START_COL += dc
    dusts[TOP_BOUNDARY][1] = 0

    # UNDER_CLEAN
    START_ROW, START_COL = UNDER_BOUNDARY, 0
    for d in range(4):
        dr, dc = DOWN_CELAN[d]
        while UNDER_BOUNDARY <= START_ROW+dr < R and -1 < START_COL+dc < C:
            dusts[START_ROW][START_COL], dusts[START_ROW+dr][START_COL+dc] = dusts[START_ROW+dr][START_COL+dc], dusts[START_ROW][START_COL]
            START_ROW += dr
            START_COL += dc
    dusts[UNDER_BOUNDARY][1] = 0

풀이2

공기청정기에 빨려들어갈 미세먼지 칸에 값을 덮어씌우면서 한칸씩 땡겼다
풀이1과는 다르게 빨려들어간 미세먼지가 아니라 공기청정기 오른쪽에 있는 칸의 값을 0으로 바꿔주면 된다. 값을 서로 바꿔주는 게 아니고 대입하는 거기 때문에 한칸씩 옆에 있는 값에 덮어씌우는 방식으로 돌아가게 되는데, 그렇게 되면 가장 첫 번째 있는 값은(공기청정기 옆칸) 덮어씌워질 값이 없어서 그대로 있게 되기 때문

def rotate(dusts, R, C):
    # 1열에 있는 미세먼지 이동(공기 청정기 바로 위쪽은 빨려들어가기 때문에 제외)
    for i in range(TOP_ROW-2, -1, -1):
        dusts[i+1][0] = dusts[i][0]
    # 1행에 있는 미세먼지 이동
    for j in range(1, C):
        dusts[0][j-1] = dusts[0][j]
    # C-1열에 있는 미세먼지 이동
    for i in range(1, TOP_ROW+1):
        dusts[i-1][C-1] = dusts[i][C-1]
    # TOP_ROW행에 있는 미세먼지 이동(0열에 있는 공기청정기는 이동할 필요 없음)
    for j in range(C-2, 0, -1):
        dusts[TOP_ROW][j+1] = dusts[TOP_ROW][j]
    dusts[TOP_ROW][1] = 0

    for i in range(UNDER_ROW+2, R):
        dusts[i-1][0] = dusts[i][0]
    for j in range(1, C):
        dusts[R-1][j-1] = dusts[R-1][j]
    for i in range(R-2, UNDER_ROW-1, -1):
        dusts[i+1][C-1] = dusts[i][C-1]
    for j in range(C-2, 0, -1):
        dusts[UNDER_ROW][j+1] = dusts[UNDER_ROW][j]
    dusts[UNDER_ROW][1] = 0

최종 코드

풀이1

# 3148ms

def FIND_DUST(dusts, R, C):
    dust_lst = {}
    for i in range(R):
        for j in range(C):
            if (dust_amount:=dusts[i][j]) > 0:
                dust_lst[(i, j)] = dust_amount

    return dust_lst

def FIND_CLENADER(dusts, R):
    for i in range(R):
        if dusts[i][0] == -1:
            return i, i+1

def speard_dust(dusts, R, C, dust_lst, new_dusts):
    dust_lst = FIND_DUST(dusts, R, C)

    for dust, amount in dust_lst.items():
        r, c = dust
        to_amount = amount // 5
        if to_amount > 0:
            for d in range(4):
                dr, dc = SPREAD_DIR[d]
                nr, nc = r+dr, c+dc
                if -1 < nr < R and -1 < nc < C and dusts[nr][nc] != -1: 
                    new_dusts[nr][nc] += to_amount
                    amount -= to_amount
            
        new_dusts[r][c] += amount

    return new_dusts

import sys
input = sys.stdin.readline

R, C, T = map(int, input().split())
dusts = [list(map(int, input().split())) for _ in range(R)]

TOP_CLEAN = ((-1, 0), (0, 1), (1, 0), (0, -1))
DOWN_CELAN = ((1, 0), (0, 1), (-1, 0), (0, -1))
SPREAD_DIR = ((1, 0), (0, 1), (-1, 0), (0, -1))

TOP_BOUNDARY, UNDER_BOUNDARY = FIND_CLENADER(dusts, R)

dust_lst = FIND_DUST(dusts, R, C)
for _ in range(T):
    new_dusts = [[0] * C for _ in range(R)]
    new_dusts[TOP_BOUNDARY][0] = -1
    new_dusts[UNDER_BOUNDARY][0] = -1

    dusts = speard_dust(dusts, R, C, dust_lst, new_dusts)
    
    # TOP_CLEAN
    START_ROW, START_COL = TOP_BOUNDARY, 0
    for d in range(4):
        dr, dc = TOP_CLEAN[d]
        while -1 < START_ROW+dr <= TOP_BOUNDARY and -1 < START_COL+dc < C:
            dusts[START_ROW][START_COL], dusts[START_ROW+dr][START_COL+dc] = dusts[START_ROW+dr][START_COL+dc], dusts[START_ROW][START_COL]
            START_ROW += dr
            START_COL += dc
    dusts[TOP_BOUNDARY][1] = 0

    # UNDER_CLEAN
    START_ROW, START_COL = UNDER_BOUNDARY, 0
    for d in range(4):
        dr, dc = DOWN_CELAN[d]
        while UNDER_BOUNDARY <= START_ROW+dr < R and -1 < START_COL+dc < C:
            dusts[START_ROW][START_COL], dusts[START_ROW+dr][START_COL+dc] = dusts[START_ROW+dr][START_COL+dc], dusts[START_ROW][START_COL]
            START_ROW += dr
            START_COL += dc
    dusts[UNDER_BOUNDARY][1] = 0
    dust_lst = FIND_DUST(dusts, R, C)

print(sum(dust_lst.values()))

풀이2

# 1612ms

def FIND_CLENADER(dusts, R):
    for i in range(R):
        if dusts[i][0] == -1:
            return i, i+1

def diffusion(dusts, R, C):
    new_dusts = [[0] * C for _ in range(R)]
    for i in range(R):
        for j in range(C):
            # 공기청정기 피하기
            if dusts[i][j] == -1:
                new_dusts[i][j] = -1
                continue

            # 굳이 미세먼지가 없는 부분은 확인하지 않음 왜냐면 많이 반복될수록 미세먼지 없는 칸이 없으므로..
            dust = dusts[i][j]
            diffusion_dust, diffusion_area = dust // 5, 0
            if i+1 < R and dusts[i+1][j] != -1:
                new_dusts[i+1][j] += diffusion_dust
                diffusion_area += 1
            if j+1 < C and dusts[i][j+1] != -1:
                new_dusts[i][j+1] += diffusion_dust
                diffusion_area += 1
            if i-1 > -1 and dusts[i-1][j] != -1:
                new_dusts[i-1][j] += diffusion_dust
                diffusion_area += 1
            if j-1 > -1 and dusts[i][j-1] != -1:
                new_dusts[i][j-1] += diffusion_dust
                diffusion_area += 1
            new_dusts[i][j] += (dust - diffusion_dust * diffusion_area)
    
    return new_dusts
                
def rotate(dusts, R, C):
    # 1열에 있는 미세먼지 이동(공기 청정기 바로 위쪽은 빨려들어가기 때문에 제외)
    for i in range(TOP_ROW-2, -1, -1):
        dusts[i+1][0] = dusts[i][0]
    # 1행에 있는 미세먼지 이동
    for j in range(1, C):
        dusts[0][j-1] = dusts[0][j]
    # C-1열에 있는 미세먼지 이동
    for i in range(1, TOP_ROW+1):
        dusts[i-1][C-1] = dusts[i][C-1]
    # TOP_ROW행에 있는 미세먼지 이동(0열에 있는 공기청정기는 이동할 필요 없음)
    for j in range(C-2, 0, -1):
        dusts[TOP_ROW][j+1] = dusts[TOP_ROW][j]
    dusts[TOP_ROW][1] = 0

    for i in range(UNDER_ROW+2, R):
        dusts[i-1][0] = dusts[i][0]
    for j in range(1, C):
        dusts[R-1][j-1] = dusts[R-1][j]
    for i in range(R-2, UNDER_ROW-1, -1):
        dusts[i+1][C-1] = dusts[i][C-1]
    for j in range(C-2, 0, -1):
        dusts[UNDER_ROW][j+1] = dusts[UNDER_ROW][j]
    dusts[UNDER_ROW][1] = 0

import sys
input = sys.stdin.readline

R, C, T = map(int, input().split())
dusts = [list(map(int, input().split())) for _ in range(R)]

TOP_ROW, UNDER_ROW = FIND_CLENADER(dusts, R)

t = 0
while t < T:
    dusts = diffusion(dusts, R, C)
    rotate(dusts, R, C)
    t += 1

answer = 2
for row in dusts:
    answer += sum(row)

print(answer)

lemythe423

아무말이나하기

이전 포스트

[BOJ] 1238. 파티(🥇, 다익스트라)

다음 포스트

[BOJ] 17144. 미세먼지 안녕! (🥇, 구현/시뮬레이션)

BOJ 문제풀이

문제

풀이

구현

최종 코드

풀이1

풀이2

[BOJ] 1238. 파티(🥇, 다익스트라)

[BOJ] 5427. 불 (🥇, BFS/DFS)

0개의 댓글