BOJ - 미세먼지 안녕! 17144번 (python)

❓ 문제 - 백준 미세먼지 안녕! 17144번 - python 풀이법

출처 

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

17144번: 미세먼지 안녕!

 

 

📝 문제해결법

1. 이 문제는 구현으로 풀었다.

• 격사판의 정보를 받을 때 공기청정기가 있는 행의 정보(위, 아래)를 저장한다.
• 1초에 대해 move_dust() 함수로 미세먼지의 확산을 한 후, move_air_up()과 move_air_down() 함수로 공기청정기를 가동시켜 공기를 순환한다.
• t초 후 graph 리스트의 미세먼지 양을 더해서 answer을 출력한다.

2. move_dust()

• 미세먼지의 확산이 동시에 일어나기 때문에, graph 리스트만을 이용해서 확산을 처리하면 중간에 값이 변경되므로 g 리스트를 이용해서 미세먼지의 확산을 구현한다.
• 격자판의 모든 행과 열을 돌면서 미세먼지가 있을 때, 4방향에서 범위에 벗어나지 않고 공기청정기 없는 방향으로 확산을 수행한다.
• 확산 수행 후 미세먼지의 옮겨진 양을 g 리스트에 저장한다.
• 모든 확산이 진행된 후  graph리스트의 값을 g리스트의 값들로 변경한다.

3. move_air_up(), move_air_down() -> 다른 블로그 참조해서 구현하였음...

• 공기청정기 윗 부분과 아랫부분의 공기 순환 방향이 다르므로 함수를 나눠서 구현하였다.
• 공기청정기 윗 부분은 반시계 반대방향으로 공기 순환하므로 공기 청정기 있는 위치에서 (동 -> 북 -> 서 -> 남) 방향으로 순환한다. 공기청정기 아랫 부분은 시계 반대방향으로 공기 순환하므로 공기 청정기 있는 위치에서 (동 -> 남 -> 서 -> 북) 방향으로 순환한다.
• 처음 방향과, 옆으로 옮겨지는 공기청정기 값은 0 이고, while문을 통해 순환을 구현하는데 만약 모든 방향으로 순환한 후 다시 공기청정기 자리까지 오면 while문을 빠져나온다.
• 해당 방향으로 이동하면서 만약 범위를 넘는다면 방향을 바꿔준다.
• 해당 방향으로 이동할 때, 현재 위치의 값을 전에 저장했던 now 값을 바꿔주고 전에 있던 값은 현재 위치의 값으로 바꿔준다.
• 현재 위치를 이동중인 방향으로 바꿔주면서 순환을 진행한다.

 

 

💻 소스코드

# 미세먼지 안녕 - BOJ 17144
# 구현r, c, t = map(int, input().split())

graph = [list(map(int, input().split())) for _ in range(r)]
m_x = []
m_x_count = 0

for i in range(r):
    if graph[i][0] == -1:
        m_x_count += 1
        m_x.append(i)
    if m_x_count == 2:
        break



def move_dust():
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    g = [[0]*c for _ in range(r)]
    for i in range(r):
        for j in range(c):
            x, y = i, j
            count = 0
            if graph[x][y] == 0:
                continue
            if graph[x][y] == -1:
                g[x][y] = -1
                continue
            for k in range(4):
                nx = x + dx[k]
                ny = y + dy[k]
                if 0 <= nx < r and 0 <= ny < c and graph[nx][ny] != -1:
                    count += 1
                    g[nx][ny] += int(graph[x][y] // 5)
            g[x][y] += (graph[x][y] - int(graph[x][y] // 5) * count)

    for i in range(r):
        for j in range(c):
            graph[i][j] = g[i][j]

def move_air_up():
    # 동 - 북- 서 - 남
    dx = [0, -1, 0, 1]
    dy = [1, 0, -1, 0]
    now, dir = 0, 0
    x, y = m_x[0], 1
    while True:
        nx = x + dx[dir]
        ny = y + dy[dir]
        if x == m_x[0] and y == 0:
            break
        if nx < 0 or nx >= r or ny < 0 or ny >= c:
            dir += 1
            continue
        graph[x][y], now = now, graph[x][y]
        x, y = nx, ny

def move_air_down():
    # 동 - 남 - 서 - 북
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    now, dir = 0, 0
    x, y = m_x[1], 1
    while True:
        nx = x + dx[dir]
        ny = y + dy[dir]
        if x == m_x[1] and y == 0:
            break
        if nx < 0 or nx >= r or ny < 0 or ny >= c:
            dir += 1
            continue

        graph[x][y], now = now, graph[x][y]
        x, y = nx, ny


for i in range(t):
    move_dust()
    move_air_up()
    move_air_down()


answer = 0

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

print(answer)