[백준] 17144 - 미세먼지 안녕!

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

17144번: 미세먼지 안녕!

문제 한줄 이해

- 그래프에 공기청정기와 미세먼지들이 있을때 1초동안 하는 일련의 과정이 진행되고 총 미세먼지 양을 구하기

생각난 풀이

1번째 방법: 문제를 읽고 생각난 필요한 조건들

1. 1초동안 어떤 과정들이 이루어지는지 파악

1-2. 각 미세먼지들이 상하좌우로 퍼진다. -> 먼지들이 있는곳을 큐에 담아 상하좌우 탐색하기

1-3. 그런다음 공기청정기에 의해 미세먼지들이 이동한다. -> 그래프에서 내가 직접 구현해야하는 부분

2. 위와 같은 일련의 과정들이 1초동안 이루어진다. -> t초 동안 반복해주기

import sys
from collections import deque

def bfs():
    que = deque()
    
    dx = [0,-1,0,1]
    dy = [1,0,-1,0]
    
    where = 0 # 청정기 위치 담아두기 위한 코드
    clearup = (0,0)
    cleardown = (0,0)
    # 먼저 1-2 조건 해결하기 위한 부분
    for i in range(r):
        for j in range(c):
            if graph[i][j] > 0:
                que.append((i,j,graph[i][j]))
            if graph[i][j] == -1:
                if where == 0:
                    clearup = (i,j)
                    where += 1
                else:
                    cleardown = (i,j)
    
    while que :
        nowx, nowy, nowv = que.popleft()
        cnt = 0
        
        for i in range(4):
            nextx = dx[i] + nowx
            nexty = dy[i] + nowy
            
            if nextx >= 0 and nexty >= 0 and nextx < r and nexty <c:
                if graph[nextx][nexty] != -1:
                    graph[nextx][nexty] += nowv//5
                    cnt += 1
        graph[nowx][nowy] -= (cnt*(nowv//5))
    
    # 공기청정기 윗부분 직접 구현
    # 위에서 dx dy 순서를 우 상 좌 하로 구현해서 그대로 가져다 씀
    nowx,nowy = clearup
    pre = 0
    for i in range(4):
        while True:
            nextx, nexty = nowx + dx[i],nowy + dy[i]
            if nextx < 0 or nexty < 0 or nextx > clearup[0] or nexty >= c:
                break
            if nextx == clearup[0] and nexty == clearup[1]:
                break
            
            temp = graph[nextx][nexty]
            graph[nextx][nexty] = pre
            pre = temp
            nowx,nowy = nextx,nexty
    
    # 공기청정기 아래부분 직접 구현
    # 주의!!!!!!!!!! 아래부분은 공기 진행방향이 달라서 다시선언
    dx = [0,1,0,-1]
    dy = [1,0,-1,0]
    nowx,nowy = cleardown
    pre = 0
    for i in range(4):
        while True:
            nextx, nexty = nowx + dx[i],nowy + dy[i]
            if nextx < cleardown[0] or nexty < 0 or nextx >= r or nexty >= c:
                break
            if nextx == cleardown[0] and nexty == cleardown[1]:
                break
            
            temp = graph[nextx][nexty]
            graph[nextx][nexty] = pre
            pre = temp
            nowx,nowy = nextx,nexty
            

r, c, t = map(int,sys.stdin.readline().split())
graph = []

for i in range(r):
    graph.append(list(map(int,sys.stdin.readline().split())))

# t초동안 반복
for i in range(t):
    bfs()

# 반복후 미세먼지 양 구하기
ans = 0
for i in range(r):
    for j in range(c):
        if graph[i][j] > 0:
            ans += graph[i][j]
print(ans)

코드에서 공기청정기의 기능을 직접 구현한 코드의 아이디어는 다음과 같다.

이전값의 그릇과 다음값의 그릇을 만들어 놓은 뒤 이전값 그릇에 값을 꺼내 다음 값에 넣어주고 다음값에 있던 값을 다시 이전값 그릇에 넣어주는 과정을 진행하면 된다. 헷갈린다면 그림을 그려보는걸 추천!

점점 난이도가 올라가면서 좀더 응용되는 문제들이 많아진다 ... 
꾸준히 연습해 나가야한다.!