17144 - 미세먼지 안녕!

 

---

 

문제

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

17144번: 미세먼지 안녕!

 

풀이

열심히 열심히 구현하면 되는 문제다.

먼지 확산관련해서 조금 헷갈렸는데, 확산되는 먼지값들은 모두 합쳐주면 되는거였다.

 

나는 함수들을 몇개 나눠서 구현했다.

 

우선 공기청정기를 기준으로 바람이 부는 방향을 다 저장하는 함수를 만들었다.

해당 방향은 내가 지정해놓은 dx, dy배열을 기준으로 방향을 저장했고, 이렇게 방향이 저장된 배열은 바람이 불 때 사용했다.

 

다음은 미세먼지의 확산 함수이다. 미세먼지가 있는 좌표라면 좌우상하 검사하고 조건에 따라 새로운 값들을 할당해주면 된다. 이 때 기존 배열을 갱신하면 값이 변하므로 모든값이 0으로 초기화된 배열을 새로 선언한후에 값을 저장해주면 된다.

 

마지막으로 바람이 불 때다, 이전에 저장해놓은 방향 배열을 이용하여서 좌표를 이동해주면 되고,

이전 좌표에 있던 미세먼지를 현재좌표의 미세먼지로 갱신해주면 된다. 그리고 공기청정기를 만나면 갱신할필요 없이 반복문을 탈출하면 된다.

 

 

코드

from sys import stdin
from collections import deque
import sys
import heapq
import copy


# 공기 청정기의 위치를 얻어둠
def getAirLocation():
    global A, r, c
    temp = []
    for i in range(r):
        for j in range(c):
            if A[i][j] == -1:
                temp.append((i,j))
    return temp

# 바람이 어디로 부는지 구하고 저장한다.
def initDirection():
    global A, direction, r, c, air

    # 공기청정기 상단 처리
    x, y = air[0]
    y += 1
    while True:
        if y == c-1: break
        direction[x][y] = 0
        y += dy[0]
    while True:
        if x == 0: break
        direction[x][y] = 1
        x += dx[1]
    while True:
        if y == 0: break
        direction[x][y] = 2
        y += dy[2]
    while True:
        if x == air[0][0]: break
        direction[x][y] = 3
        x += dx[3]

    # 공기청정기 하단 처리
    x, y = air[1]
    y += 1
    while True:
        if y == c-1: break
        direction[x][y] = 0
        y += dy[0]
    while True:
        if x == r-1: break
        direction[x][y] = 3
        x += dx[3]
    while True:
        if y == 0 : break
        direction[x][y] = 2
        y += dy[2]
    while True:
        if x == air[1][0]: break
        direction[x][y] = 1
        x += dx[1]

# 미세먼지를 퍼트리고, 결과 배열을 return 한다.
def spread():
    global A, r, c
    
    # 각 좌표에 퍼진 값, 그리고 각 좌표에 남은값을 따로 저장해두자.
    res = [[0] * c for _ in range(r)]

    for x in range(r):
        for y in range(c):
            if A[x][y] == -1: res[x][y] = -1

            # 해당 칸이 미세먼지 칸이라면
            if A[x][y] != 0 and A[x][y] != -1:
                val = A[x][y] // 5
                count = 0
                for k in range(4):
                    nx = x + dx[k]
                    ny = y + dy[k]

                    # 퍼질려는곳이 범위 안이면서, 공기청정기가 위치한곳이 아니라면
                    # -> 확산 횟수 카운트 및, 나누기 5한 값을 저장해준다.
                    if 0 <= nx < r and 0 <= ny < c and A[nx][ny] != -1:
                        count += 1
                        res[nx][ny] += val
                res[x][y] += (A[x][y] - (val * count))
    return res

# 바람이 분다.
def blow():
    global A, air
    for position in air:
        before = 0
        x, y = position
        y += 1
        while True:
            # 공기청정기라면, 갱신해주지 않고 빠져나온다.
            if A[x][y] == -1:
                break

            now = A[x][y]
            A[x][y] = before
            before = now

            nx = x + dx[direction[x][y]]
            ny = y + dy[direction[x][y]]
            x = nx
            y = ny


# Initialize -> 우, 상, 좌, 하
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]

r, c, t = map(int,input().split())
A = [ list(map(int, stdin.readline().rstrip().split())) for _ in range(r) ]
direction = [[9] * c for _ in range(r)]
air = getAirLocation()
initDirection()

for i in range(t):
    A = spread()
    blow()

answer = 0
for i in range(r):
    for j in range(c):
        if A[i][j] != -1:
            answer += A[i][j]
print(answer)

 

후기

 

변수 위치 하나를 잘못잡아서 예상외로 시간이 오래걸렸다. 운좋게 반례를 찾아서 다행이지 아니였다면... 끔찍하다.

구현은 언제나 섬세함 꼼꼼함 ...  

 

+ 방향을 저장하는 배열을 선언하고 값을 구했는데 사실 바람 불 때 한번에 처리해도 큰 상관은 없을 거 같다.