[알고리즘/구현] 17144번 : 미세먼지 안녕! - python

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

17144번: 미세먼지 안녕!

 

---

• 문제
• 소요시간: 1시간 0분 54초

---

• 설계하기(접근방법) 

1. 입력받기

미세먼지 배열을 입력받는다

 

2. 구현하기

문제의 요구대로 구현하면 된다

 

미세먼지의 확산은 동시에 일어난다

즉 순서대로 확산시키는 즉시 graph에 반영시키면

다음 확산에 영향을 미칠 수 있다

 

따라서 먼저 미세먼지가 있는 [i,j, 미세먼지 농도]를 저장한 후

그 리스트로 접근해서 미세먼지를 확산시켜야 한다

 

주의해야하는 점은 미세먼지가 바람을 따라 순회할 때

리스트를 초과하지 않도록 잘 조절해야 한다

 

3. 출력하기

위의 요구사항을 지키면서 t번 수행한 후 전체 미세먼지의 수를 출력한다

 

 

---

• 코드(출력)

def clean_dust_up():
    x, y = air_clean[0]
    # 청청기 윗칸 처리
    x = x-1
    graph[x][y] = 0

    while x > 0:
        graph[x][y] = graph[x - 1][y]
        x -= 1
    y = y + 1

    while y < m:
        graph[x][y - 1] = graph[x][y]
        y += 1
    y = y - 1

    while x < air_clean[0][0]:
        graph[x][y] = graph[x + 1][y]
        x += 1

    while y > 1:
        graph[x][y] = graph[x][y-1]
        y -= 1
    graph[x][y] = 0
def clean_dust_down():
    x, y = air_clean[1]
    x = x + 1
    graph[x][y] = 0

    while x < n - 1 :
        graph[x][y] = graph[x + 1][y]
        x = x + 1
    y = y + 1

    while y < m:
        graph[x][y - 1] = graph[x][y]
        y += 1
    y = y - 1

    while x > air_clean[1][0]:
        graph[x][y] = graph[x - 1][y]
        x -= 1

    while y > 1:
        graph[x][y] = graph[x][y-1]
        y -= 1
    graph[x][y] = 0




n , m, t = map(int, input().split())
dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]
graph =[list(map(int, input().split())) for _ in range(n)]

for i in range(t):
    air_clean = []
    dust_location = []
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 0:
                continue
            if graph[i][j] == -1:
                air_clean.append([i, j])
            else:
                dust_location.append([i, j, graph[i][j]])

    while dust_location:
        x, y, dust = dust_location.pop()
        # 확산 카운트
        cnt = 0
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<= nx < n and 0 <= ny < m:
                if graph[nx][ny] != -1:
                    graph[nx][ny] += (dust // 5)
                    cnt += 1
        graph[x][y] -= (dust // 5) * cnt

    clean_dust_up()
    clean_dust_down()

dust_cnt = 0
for i in range(n):
    for j in range(m):
        if graph[i][j] == -1:
            continue
        else:
            dust_cnt += graph[i][j]
            
print(dust_cnt)

---

• 얻어갈 부분

1. 꾸준히 출력을 통해 미리 디버깅을 해서 문제가 없었다