[BOJ] 17144. 미세먼지 안녕!

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

17144번: 미세먼지 안녕!

 

 

1. 해결방법

"""
1. 아이디어
- 공기 청정기의 위치를 확인하여 위쪽에 해당하는 위치를 front에 할당하고, 아래쪽에 위치는 위쪽 위치에 1을 더한 값을 back에 할당.
- 입력받은 T초 만큼 확산 함수(spread())를 실행, 공기청정기 함수 실행 -> 위쪽 (air_up()), 아래쪽 (air_down())
- R * C 크기의 2치원 배열 graph를 생성
- 반복문을 돌아서 그래프 원소를 방문해서 미세먼지가 존재하면 확한 함수를 실행
- 확산과 공기청정기 함수를 T초만큼 실행시키고 방에 남아있는 미세먼지의 양을 result 값에 누적시켜 출력.
"""

 

2. 정답코드

입력 예제는 백준저지에서...

 

코드

import sys
input = sys.stdin.readline


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

front, back = 0, 0

# 공기 청정기 위치 확인
for i in range(R):
    if graph[i][0] == -1:
        front = i
        back = i + 1
        break


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

    temp = [[0] * C for _ in range(R)]
    for i in range(R):
        for j in range(C):
            if graph[i][j] != 0 and graph[i][j] != -1:
                value = 0
                for k in range(4):
                    ny, nx = i + dy[k], j + dx[k]
                    if 0 <= ny < R and 0 <= nx < C and graph[ny][nx] != -1:
                        temp[ny][nx] += graph[i][j] // 5
                        value += graph[i][j] // 5
                graph[i][j] -= value

    for i in range(R):
        for j in range(C):
            graph[i][j] += temp[i][j]


# 공기 청정기 위쪽
def air_up():
    dy = [0, -1, 0, 1]
    dx = [1, 0, -1, 0]
    y, x = front, 1
    dis = 0
    before = 0

    while True:
        ny, nx = y + dy[dis], x + dx[dis]
        if y == front and x == 0:
            break
        if not 0 <= ny < R or not 0 <= nx < C:
            dis += 1
            continue
        graph[y][x], before = before, graph[y][x]
        y, x = ny, nx


# 공기 청정기 아래쪽
def air_down():
    dy = [0, 1, 0, -1]
    dx = [1, 0, -1, 0]
    y, x = back, 1
    dis = 0
    before = 0

    while True:
        ny, nx = y + dy[dis], x + dx[dis]
        if y == back and x == 0:
            break
        if not 0 <= ny < R or not 0 <= nx < C:
            dis += 1
            continue
        graph[y][x], before = before, graph[y][x]
        y, x = ny, nx


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

result = 0
for i in range(R):
    for j in range(C):
        if graph[i][j] > 0:
            result += graph[i][j]

print(result)

 

이번문제 역시 풀지 못했다.
spread() 확산 함수에서 temp 2차원 배열을 하나 두어서 확산된 미세먼지를 처리하는 방법을 생각하지 못하였고,
공기청정기의 미세먼지의 이동하는 함수 자체를 이해하지 못해서 많이 해메고, 검색을 했다...

아직 갈 길이 멀다는 것을 느꼈다.