[백준 17144번-미세먼지 안녕!]-파이썬

solved.ac 난이도 :  GOLD4

백준  17144번- 파이썬 풀이

 

<문제>

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

17144번: 미세먼지 안녕!

<풀이>-구현,시뮬레이션

 

이 문제를 풀때 가장 중요한것은 두가지다. 첫번째는 모든 구역에서 확산이 동시에 일어난다는 것, 그리고 미세먼지가 있는 구역에도 확산이 일어난다는 것이다.

 

 

문제를 풀때 미세먼지를 확산시키는 함수, 공기청정기를 작동시키는 함수를 따로따로 구현해 보았다.

먼저 미세먼지를 확산시키는 함수를 살펴보자.

 

 

먼저나는 이부분을 구현할때 bfs알고리즘을 떠올렸다. 하지만 모든 구역에서 동시에 확산이 일어난다는 점에서 bfs를 사용하기에는 무리가 있었다.

 

 

따라서 temp라는 모든 원소가 0인배열을 정의하고 각각의 구역에서 확산이 일어난 후의 상황을  temp에 저장하는 방법을 사용했다.

 

def bfs(x,y):
    dust =0
    count = 0
    dx = [-1,0,1,0]
    dy = [0,-1,0,1]
    if graph[x][y]!=0 and graph[x][y]!=-1:
        dust = graph[x][y]//5
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0<=nx<r and 0<=ny<c
            	if graph[nx][ny]!=-1:
                   count+=1
                   temp[nx][ny] +=dust
        temp[x][y]+=graph[x][y]-dust*count
        for i in condi:
            temp[i][0] = -1
    return temp

 

다음은 공기청정기를 작동시키는 함수이다. 이부분은 그래프의 인덱스에 대한 개념만 충분하다면 크게 어렵진 않았다.여기서 가장중요했던것은 함수의 매개변수를 설정하는 것이었다.

 

 

 

만약 2초동안 반복해야한다면 2초일때는1초후의 상황을 담은 그래프를 사용해야한다.

 

 

 

따라서 이 함수에서 매개변수를 어떻게 설정해야 초기상황의 그래프에  변화된 상황을 적용시킬수 있는지에 대한 고민을 많이 했다.

def air(graph,new_graph):
    for i in range(0,len(graph[a])-1):
        graph[a][i+1] = new_graph[a][i]
        if new_graph[a][i] == -1:
            graph[a][i+1] = 0
    for i in range(1,len(graph[0])):
        graph[0][i-1] = new_graph[0][i]
    for i in range(0,a-1):
        graph[i+1][0] = new_graph[i][0]
    for i in range(0,a):
        graph[i][c-1] = new_graph[i+1][c-1]
    for i in range(1,a):
        for j in range(1,c-1):
            graph[i][j] = new_graph[i][j]
    # 아래쪽 공기청정기
    for i in range(0,len(graph[b])-1):
        graph[b][i+1] = new_graph[b][i]
        if new_graph[b][i] == -1:
            graph[b][i+1] = 0

    for i in range(1,len(graph[r-1])):
        graph[r-1][i-1] = new_graph[r-1][i]

    for i in range(b+1,r-1):
        graph[i][0] = new_graph[i+1][0]
    for i in range(b,r-1):
        graph[i+1][c-1] = new_graph[i][c-1]
    for i in range(b+1,r-1):
        for j in range(1,c-1):
            graph[i][j] = new_graph[i][j]
    for i in condi:
        graph[i][0] = -1

이 코드에서 매개변수 new_graph란 초기 그래프에서 미세먼지가 확산된 상황을 의미한다.

 

 

 

그리고 위 함수가 의미하는 바는 확산된 상황인 new_graph에서 공기청정기가 작동된 이후의 상황을 graph에 반영하는것을 의미한다.

 

 

 

그렇게 되면 graph는 초기상태와 다르게 공기청정기가 작동된 이후의 상황으로 바뀌게 된다.

(a,b : 공기청정기의 위치)

 

 

 

728x90

 

 

<코드>-파이썬

r,c,t, = map(int,input().split())
graph = []
import copy
for _ in range(r):
    graph.append(list(map(int,input().split())))

condi = []
for i in range(r):
    if graph[i][0] == -1:
        condi.append(i)
temp = [[0]*c for _ in range(r)]
def bfs(x,y):
    dust =0
    count = 0
    dx = [-1,0,1,0]
    dy = [0,-1,0,1]
    if graph[x][y]!=0 and graph[x][y]!=-1:
        dust = graph[x][y]//5
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0<=nx<r and 0<=ny<c
               if graph[nx][ny]!=-1:
                  count+=1
                  temp[nx][ny] +=dust
        temp[x][y]+=graph[x][y]-dust*count
        for i in condi:
            temp[i][0] = -1
    return temp
a = condi[0]
b = condi[1]
def air(graph,new_graph):
    for i in range(0,len(graph[a])-1):
        graph[a][i+1] = new_graph[a][i]
        if new_graph[a][i] == -1:
            graph[a][i+1] = 0
    for i in range(1,len(graph[0])):
        graph[0][i-1] = new_graph[0][i]
    for i in range(0,a-1):
        graph[i+1][0] = new_graph[i][0]
    for i in range(0,a):
        graph[i][c-1] = new_graph[i+1][c-1]
    for i in range(1,a):
        for j in range(1,c-1):
            graph[i][j] = new_graph[i][j]
    # 아래쪽 공기청정기
    for i in range(0,len(graph[b])-1):
        graph[b][i+1] = new_graph[b][i]
        if new_graph[b][i] == -1:
            graph[b][i+1] = 0

    for i in range(1,len(graph[r-1])):
        graph[r-1][i-1] = new_graph[r-1][i]

    for i in range(b+1,r-1):
        graph[i][0] = new_graph[i+1][0]
    for i in range(b,r-1):
        graph[i+1][c-1] = new_graph[i][c-1]
    for i in range(b+1,r-1):
        for j in range(1,c-1):
            graph[i][j] = new_graph[i][j]
    for i in condi:
        graph[i][0] = -1


while t!=0:
    for i in range(r):
        for j in range(c):
            new_graph = bfs(i,j)
    air(graph,new_graph)
    temp = [[0]*c for _ in range(r)]
    t-=1
result = 0
for i in range(r):
    for j in range(c):
        if graph[i][j]!=-1:
            result+=graph[i][j]
print(result)

-while문 설명-

1초마다 확산과 공기청정기를 작동해야하므로 while t!=0을 사용했다.

 

 

new_graph는 위에서 설명한대로 미세먼지가 확산된 이후의 상황이고 그때마다 air함수를 사용해 공기청정기가 작동된 이후의 상황을 graph에 반영한다.

 

 

그리고 매초가 지날때마다 새로운 확산이 일어나므로 이를 저장할 배열 temp를 초기화 시켜준다.

 

 

-마치며-

 

이 문제는 함수를 짜고나서 함수의 반환값을 어떻게 설정해하는지에 대한 고민때문에 많은 어려움을 겪었다. 예를들어 3초동안 반복해야한다면 매초마다 그래프를 갱신해야하는데 이 부분이 쉽지 않았다.

때문에 처음에 쉽게 생각했다가 시간을 꽤 오래 잡아먹었다.

앞으로 파이썬의 메서드 부분을 좀더 열심히 해봐야겠다.