[BOJ] 17144 : 미세먼지 안녕 [시뮬레이션](Python)

문제 링크

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

17144번: 미세먼지 안녕!

소스 코드

from copy import deepcopy
import sys

def main():
    R,C,T = map(int, input().split()) # 행,열,케이스
    machine = [] # 공기청정기
    graph = [] # 전체 격자판

    for i in range(R):
        temp = list(map(int, sys.stdin.readline().strip().split()))
        if temp[0] == -1: # 공기청정기
            machine.append(i)
        graph.append(temp)

    dx = [0,0,1,-1] # 우,좌,하,상
    dy = [1,-1,0,0]
    for i in range(T):
        dust_list = dust_where(graph,R,C)
        board = deepcopy(graph) # 임시 격자판 복사
        for x,y in dust_list:
            temp = graph[x][y]//5 # 확산량(원래 그래프)
            for j in range(4): # 4방향
                nx,ny = x+dx[j], y+dy[j]
                # 범위 만족 & 공기청정기 아닌 경우
                if 0<=nx<R and 0<=ny<C and graph[nx][ny] != -1:
                    board[nx][ny] += temp # 복사그래프
                    board[x][y] -= temp

        upper_x,lower_x= machine[0],machine[1] # 공기청정기

        for j in range(upper_x-1,0,-1): # 문제에서 주어진 것과 반대 순서로
            board[j][0] = board[j-1][0]
        for j in range(C-1):
            board[0][j] = board[0][j+1]
        for j in range(upper_x):
            board[j][-1] = board[j+1][-1]
        for j in range(C-1,1,-1):
            board[upper_x][j] = board[upper_x][j-1]
        board[upper_x][1] = 0 # 청정기 바로 옆

        for j in range(lower_x+1,R-1): # 문제에서 주어진 것과 반대 순서로
            board[j][0] = board[j+1][0]
        for j in range(C-1):
            board[-1][j] = board[-1][j+1]
        for j in range(R-1,lower_x,-1):
            board[j][-1] = board[j-1][-1]
        for j in range(C-1,1,-1):
            board[lower_x][j] = board[lower_x][j-1]
        board[lower_x][1] = 0 # 청정기 바로 옆
        
        graph = board # 원래 그래프로 가져오기
    print(sum(sum(graph,[]))+2) # 최종 결과 + 2(공기청정기)

def dust_where(graph,R,C):
    dust_list = []
    for row in range(R): # 그래프 탐색
        for col in range(C):
            if graph[row][col] != 0 and graph[row][col] != -1:
                dust_list.append((row,col)) # 미세먼지 위치
    return dust_list

if __name__ == "__main__":
    main()

 

해설

• 시뮬레이션, 그래프

사소한 것 하나 때문에 논리에 맞게 코드를 구현해놓고도 계속해서 예시 문제도 틀리고 있었습니다 ㅜㅜ

deepcopy를 써서 기존의 그래프를 복사해야 논리적 오류가 발생하지 않는다는 것..!

물론 함수를 쓰지 않아도 그냥 그래프 값을 하나씩 추가해도 상관은 없습니다.

 

1. 공기청정기 위치 저장

공기 청정기는 반드시 1열(인덱스로는 0)에 위치한다고 문제에 명시되어 있습니다.

따라서 리스트로 입력을 받되, 그 첫 번째 값이 -1인 경우 따로 저장해둡니다.

여기서 저장하는 i는 행의 인덱스입니다.

for i in range(R):
    temp = list(map(int, sys.stdin.readline().strip().split()))
    if temp[0] == -1: # 공기청정기
        machine.append(i)
    graph.append(temp)

 

2. 미세먼지 확산

우선 미세먼지를 구하는 함수를 사용해서 현재의 위치를 파악합니다.

그리고 현재 시점의 미세먼지를 기준으로 확산을 시켜주면 됩니다.

이렇게 따로 구하는 이유는 확산은 동시에 일어나는 것이기 때문에 현재 시점을 파악해둬야 하는 것입니다.

그렇지 않으면 현재 시점에서 확산된 것이 또 확산되고 또 확산될 수 있기 때문이죠!

def dust_where(graph,R,C):
    dust_list = []
    for row in range(R): # 그래프 탐색
        for col in range(C):
            if graph[row][col] != 0 and graph[row][col] != -1:
                dust_list.append((row,col)) # 미세먼지 위치
    return dust_list

 

미세먼지는 네 방향으로 확산될 수 있습니다.

이건 마치 DFS/BFS 유형을 풀 때처럼 조건을 주면 됩니다.

그래서 nx, ny가 주어진 그래프의 범위를 벗어나지 않으면서 & 그래프의 해당 좌표값이 -1이 아닌 경우(공기청정기)를 걸러냅니다.

만약에 위 두 조건을 만족하게 되면 그 nx, ny 좌표로 확산을 하면 됩니다.

 

이때 주의할 것은 확산하는 과정을 원본 그래프에 그대로 담게 되면, 이후에 다른 미세먼지 확산에 영향을 줄 수 있다는 것입니다.

예를 들어 [0, 20, 10] 이 있다고 가정하겠습니다.

 

처음엔 20을 중심으로 확산이 진행됩니다.

따라서 그 결과는 [4, 12, 14] 가 됩니다.

 

다음으로는 10을 중심으로 확산을 해야 하는데, 기존의 20으로부터 확산된 미세먼지의 값들 때문에 확산량이 영향을 받게 됩니다.

물론 이 경우는 10//5 = 2 = 14//5 로 같기 때문에 총 합계에는 영향을 주지 않을 것입니다.

하지만 중간 값이 20이 아니라 50이었다면 확산된 값도 10으로 영향을 줄 수 있습니다.

 

따라서 확산할 때 값을 원본 그래프가 아니라 임시 그래프(board)에 반영하고, 이때 확산의 정도는 원본 그래프를 기준으로 삼는 것입니다.

그리고 모든 연산이 끝나고 나면 임시 그래프(board)의 값을 원본 그래프(graph)로 옮기면 됩니다.

dx = [0,0,1,-1] # 우,좌,하,상
dy = [1,-1,0,0]
for i in range(T):
    dust_list = dust_where(graph,R,C)
    board = deepcopy(graph) # 임시 격자판 복사
    for x,y in dust_list:
        temp = graph[x][y]//5 # 확산량(원래 그래프)
        for j in range(4): # 4방향
            nx,ny = x+dx[j], y+dy[j]
            # 범위 만족 & 공기청정기 아닌 경우
            if 0<=nx<R and 0<=ny<C and graph[nx][ny] != -1:
                board[nx][ny] += temp # 복사그래프
                board[x][y] -= temp

 

3. 공기청정기 가동

이 부분이 영 깔끔하지 않아서 그냥 함수로 구현하고 호출할까 하다가.. 귀찮아서 그냥 했습니다!

여기는 약간의 생각이 필요한데요, 공기청정기가 바람을 부는 반대 방향으로부터 값을 갱신해야 합니다.

 

문제 조건에는 맞지 않지만 작은 사각형을 예시를 들어보겠습니다.

 

[0, 1, 2, 3]

[-1,4, 5, 6]

만약 위처럼 미세먼지와 공기청정기가 배치되어 있다면, 공기청정기의 작동 결과는 다음과 같습니다.

 

[1, 2, 3, 6]

[-1,0, 4, 5]

 

원래는 -1을 중심으로 '오른쪽 -> 위쪽 -> 왼쪽 -> 아래쪽' 방향으로 돌게 되는데 이를 완전히 뒤집어 생각해보죠.

즉, -1을 중심으로 '위쪽 -> 오른쪽 -> 아래쪽 -> 왼쪽' 순서로 값을 '한 칸씩 당겨오는 것'입니다.

 

만약 값을 기존의 방향대로 밀어주게 된다면 맨 끝의 값이 사라지게 되어 따로 저장을 해야합니다.

위 예시에서 처음에 오른쪽으로 값을 다 밀어버리게 되면 두 번째 줄의 6이 없어지죠.

사실 이 6은 첫째 줄로 올라가야 하기 때문에 이 6을 임시 변수에 따로 저장해줘야 합니다.

반대로 생각해본다면 이 6의 값이 두 번째 줄을 오른쪽으로 밀기 전에 이미 첫째 줄에 와있어야 한다는 것이죠!

 

그렇기 때문에 값을 공기청정기 중심으로 하나씩 당겨오면 됩니다.

이 과정에서 주의할 것은 '범위'가 됩니다.

또한 공기청정기의 바로 우측은 공기청정기가 바람을 불어 비어있기 때문에 반드시 0이 됩니다.

이런 과정을 공기청정기 위, 아래 방향에 동일하게 적용하면 됩니다.

upper_x,lower_x= machine[0],machine[1] # 공기청정기

for j in range(upper_x-1,0,-1): # 문제에서 주어진 것과 반대 순서로
    board[j][0] = board[j-1][0]
for j in range(C-1):
    board[0][j] = board[0][j+1]
for j in range(upper_x):
    board[j][-1] = board[j+1][-1]
for j in range(C-1,1,-1):
    board[upper_x][j] = board[upper_x][j-1]
board[upper_x][1] = 0 # 청정기 바로 옆

for j in range(lower_x+1,R-1): # 문제에서 주어진 것과 반대 순서로
    board[j][0] = board[j+1][0]
for j in range(C-1):
    board[-1][j] = board[-1][j+1]
for j in range(R-1,lower_x,-1):
    board[j][-1] = board[j-1][-1]
for j in range(C-1,1,-1):
    board[lower_x][j] = board[lower_x][j-1]
board[lower_x][1] = 0 # 청정기 바로 옆

 

4. 결과 출력하기

이전에 말씀드렸던 것처럼 우리는 이 모든 계산을 '임시 그래프(board)'에 수행했습니다.

따라서 이를 원본 그래프로 가져옵니다.

 

마지막으로 값을 출력할 때는 sum함수를 사용하여 간단하게 표현할 수 있습니다.

graph는 이중 리스트이므로 이를 [ ]과 sum 하게 되면 내부 리스트들의 값이 한 리스트에 모이게 됩니다.

예를 들어 my_list = [[1],[2],[3]] 인 경우 sum(my_list, []) 를 실행하면 [1, 2, 3] 이 반환됩니다.

이제 여기에 sum 함수를 한 번 더 적용하면 이중 리스트에 포함되었던 모든 원소들의 합을 구할 수 있게 되죠.

 

단, 우리의 그래프엔 공기청정기 -1이 두 개 포함되어 있기 때문에 총합에 2를 더한 것을 정답으로 출력하면 됩니다!

    graph = board # 원래 그래프로 가져오기
print(sum(sum(graph,[]))+2) # 최종 결과 + 2(공기청정기)