[백준/Python] 17144번_미세먼지 안녕!

📌문제 유형

구현, 시뮬레이션

 

📌문제

17144번: 미세먼지 안녕!

 

📌나의 문제풀이

1. 미세먼지 확산 : 동시에 확산 -> v1(현 위치 값만 조정), v2(확산되는 값만 누적)를 각각 구하여 나중에 합하기

2. 공기청정기 : 위, 아래로 나누어서 반시계, 시계 회전(현재, 다음값 지정 후 옮기기)

r,c,t = map(int,input().split())

maps = []
air = []
for k in range(r):
    list_ = list(map(int,input().split()))
    maps.append(list_)
    if -1 in list_:
        air.append([k,0])

def micro(x,y):
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]

    cnt = 0
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < r and 0 <= ny < c and [nx, ny] not in air:
            cnt += 1
            v2[nx][ny] += int(maps[x][y] / 5)
    v1[x][y] = maps[x][y] - int(maps[x][y] / 5) * cnt



while t > 0:
    t -= 1
    # 미세먼지 확산.
    v1 = [[0 for _ in range(c)] for _ in range(r)]  # 위치 최종값
    v2 = [[0 for _ in range(c)] for _ in range(r)]  # 주변 확산

    # 위치 최종값, 주변합산 각각
    for x in range(r):
        for y in range(c):
            if maps[x][y] > 0:
                micro(x,y)

    for u in range(r):
        for v in range(c):
            maps[u][v] = v1[u][v] + v2[u][v]

    # print(maps)

    # 공기청정기 작동
    # 위쪽
    now = maps[air[0][0]][1]
    maps[air[0][0]][1] = 0
    for i in range(2,c):
        next = maps[air[0][0]][i]
        maps[air[0][0]][i] = now
        now = next
    
    for k in range(air[0][0]-1,-1,-1):
        next = maps[k][c-1]
        maps[k][c-1] = now
        now = next

    for l in range(c-2, -1,-1):
        next = maps[0][l]
        maps[0][l] = now
        now = next

    for j in range(1,air[0][0]):
        next = maps[j][0]
        maps[j][0] = now
        now = next
    # print()
    # print(maps)
    
    #아래쪽
    now = maps[air[1][0]][1]
    maps[air[1][0]][1] = 0
    for i in range(2,c):
        next = maps[air[1][0]][i]
        maps[air[1][0]][i] = now
        now = next

    for k in range(air[1][0]+1, r):
        next = maps[k][c-1]
        maps[k][c-1] = now
        now = next
    
    for l in range(c-2, -1,-1):
        next = maps[r-1][l]
        maps[r-1][l] = now
        now = next

    for j in range(r-2, air[1][0], -1):
        next = maps[j][0]
        maps[j][0] = now
        now = next
    # print(maps)
    # print()
        
# print(maps)
ans = 0
for a in range(r):
    ans += sum(maps[a])
print(ans)

 

📌다른사람의 문제풀이

- 공기청정기 방향 이동해서 풀이

import sys

input = sys.stdin.readline

r, c, t = map(int, input().split())

arr = [list(map(int, input().split())) for _ in range(r)]

up = -1
down = -1
# 공기 청정기 위치 찾기
for i in range(r):
    if arr[i][0] == -1:
        up = i
        down = i + 1
        break

# 미세먼지 확산
def spread():
    dx = [-1, 0, 0, 1]
    dy = [0, -1, 1, 0]

    tmp_arr = [[0] * c for _ in range(r)]
    for i in range(r):
        for j in range(c):
            if arr[i][j] != 0 and arr[i][j] != -1:
                tmp = 0
                for k in range(4):
                    nx = dx[k] + i
                    ny = dy[k] + j
                    if 0 <= nx < r and 0 <= ny < c and arr[nx][ny] != -1:
                        tmp_arr[nx][ny] += arr[i][j] // 5
                        tmp += arr[i][j] // 5
                arr[i][j] -= tmp

    for i in range(r):
        for j in range(c):
            arr[i][j] += tmp_arr[i][j]

# 공기청정기 위쪽 이동
def air_up():
    dx = [0, -1, 0, 1]
    dy = [1, 0, -1, 0]
    direct = 0
    before = 0
    x, y = up, 1
    while True:
        nx = x + dx[direct]
        ny = y + dy[direct]
        if x == up and y == 0:
            break
        if nx < 0 or nx >= r or ny < 0 or ny >= c:
            direct += 1
            continue
        arr[x][y], before = before, arr[x][y]
        x = nx
        y = ny

# 공기청정기 아래쪽 이동
def air_down():
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    direct = 0
    before = 0
    x, y = down, 1
    while True:
        nx = x + dx[direct]
        ny = y + dy[direct]
        if x == down and y == 0:
            break
        if nx < 0 or nx >= r or ny < 0 or ny >= c:
            direct += 1
            continue
        arr[x][y], before = before, arr[x][y]
        x = nx
        y = ny


for _ in range(t):
    spread()
    air_up()
    air_down()

answer = 0
for i in range(r):
    for j in range(c):
        if arr[i][j] > 0:
            answer += arr[i][j]

print(answer)

 

📌리뷰

- 삼성 문제는 조건 하나하나 세심히 보기! (미세먼지 동시에 확산된다는 조건 안봐서 다시 풀었음)

- 공기 청정기 방향 돌아가며 회전...(처음에 시계방향 순차적으로 숫자 없어지는걸로 이해)