[백준] 17144 미세먼지 안녕! [Python]

 

이 문제는 구현문제로 그래프 탐색과 더불어서 풀었습니다.

 

처음에는 미세먼지가 확산하는 부분까지는 기존 bfs문제들과 비슷해서 작성할 수 있었는데 이 문제에서는 공기청정기 윗 부분과 아랫 부분을 나눠서 한칸씩 밀려나가는 것을 구현하는 부분이 어려웠습니다.

 

머릿속으로는 벽에 부딪히면 방향을 전환하고 값들을 하나씩 이동시키는 형식으로 구현하면되겠다라고 생각은 드는데 막상 구현을 하자니 어디서부터 어떻게 구현해야하는지가 어려웠던 것 같습니다.

 

 

    R,C,T = map(int,s.readline().split())
    arr = [list(map(int,s.readline().split())) for _ in range(R)]
    
    #로봇의 위치 저장하는 배열
    machine=[]
    
    #미세먼지 누적 합 저장
    result=0
    
    #동남서북 4방향
    dx = [0,1,0,-1]
    dy = [1,0,-1,0]

    
    #로봇의 위치찾아서 machine 배열에 저장
    for i in range(R):
        for j in range(C):
            if arr[i][j] == -1:
                machine.append((i,j))
                
    
    #입력받은 T만큼 반복
    for _ in range(T):
        spread()
        clean_up()
        clean_down()
    
    #미세먼지의 양을 찾아서 result에 누적함
    for i in range(R):
        for j in range(C):
            if arr[i][j] != 0 and arr[i][j] != -1:
                result += arr[i][j]
    
    print(result)

 

 

우선 위 코드는 메인부분의 코드입니다. 주어진 예제처럼 입력을 받고 방향 전환을 위한 dx, dy를 선언합니다.

그리고 시간인 T가 주어지므로 T를 반복문으로 작성해서 T만큼 함수들이 실행되게끔 구현했습니다. 그리고 함수들의 실행이 끝나고 나면 전체 미세먼지의 양을 구해서 출력해줍니다.

 

 

#미세먼지 확산시키는 함수
def spread():  
    v=[[0]*C for _ in range(R)]
    
    #4방향 검사 후 v배열에 값들을 저장해둔다.
    for i in range(R):
        for j in range(C):
            if arr[i][j] != 0 and arr[i][j] != -1:
                for k in range(4):
                    nx = i+dx[k]
                    ny = j+dy[k]
                    
                    if 0<=nx<R and 0<=ny<C and arr[nx][ny] != -1:
                        mungi = arr[i][j] // 5
                        v[nx][ny] += mungi
                        v[i][j] -= mungi
    
    #위의 검사가 끝나고난 후 arr에 v배열 값들을 합침
    for i in range(R):
        for j in range(C):
            arr[i][j]+=v[i][j]

 

이 코드는 미세먼지를 확산시키는 함수로 미세먼지들을 한번에 다 확산시켜야하니 v배열에 각각의 값들을 저장해두고 전체 미세먼지가 확산이 다 끝나면 arr배열과 v배열의 값들을 합쳐서 저장해줍니다.

 

 

#공기청정기 위에부분 청소
def clean_up():
    #동쪽부터시작하니 d=0
    d=0
    before=0
    #로봇의 시작부분 다음칸부터 시작
    x, y = machine[0][0],machine[0][1]+1
    
    #로봇이 공기청정기를 만나거나 벽을만나면 방향을 꺾는 조건문 추가
    while True:
        nx = x+dx[d]
        ny = y+dy[d]
        
        if nx == R or ny == C or nx == -1 or ny == -1:
            d = (d-1)%4
            continue
        
        if x == machine[0][0] and y == machine[0][1]:
            break
        
        arr[x][y], before = before, arr[x][y]
        x,y = nx,ny

 

#공기청정기 아래부분 청소
def clean_down():
    #동쪽부터시작하니 d=0
    d=0
    before=0
    
    #로봇의 시작부분 다음칸부터 시작
    x,y = machine[1][0],machine[1][1]+1
    
    #로봇이 공기청정기를 만나거나 벽을만나면 방향을 꺾는 조건문 추가
    while True:
        nx = x+dx[d]
        ny = y+dy[d]
        
        if nx == R or ny == C or nx == -1 or ny == -1:
            d = (d+1)%4
            continue
            
        if x == machine[1][0] and y ==machine[1][1]:
            break
        
        arr[x][y],before = before,arr[x][y]
        x,y=nx,ny

 

위의 코드들은 공기청정기 윗부분을 청소하는 함수와 공기청정기 아랫부분을 청소하는 함수로 나눠서 구현했습니다.

우선 공기청정기의 위치를 저장해서 그 다음칸부터 진행을 시작했고 한 방향으로 쭉 이동하다가 벽을 만나면 방향을 전환해서 공기청정기 위치가 도달하면 종료되게 구현했습니다.

 

 

전체 코드

from sys import stdin as s
s=open('input.txt','rt')

#미세먼지 확산시키는 함수
def spread():  
    v=[[0]*C for _ in range(R)]
    
    #4방향 검사 후 v배열에 값들을 저장해둔다.
    for i in range(R):
       for j in range(C):
            if arr[i][j] != 0 and arr[i][j] != -1:
                for k in range(4):
                    nx = i+dx[k]
                    ny = j+dy[k]
                    
                    if 0<=nx<R and 0<=ny<C and arr[nx][ny] != -1:
                        mungi = arr[i][j] // 5
                        v[nx][ny] += mungi
                        v[i][j] -= mungi
    
    #위의 검사가 끝나고난 후 arr에 v배열 값들을 합침
    for i in range(R):
        for j in range(C):
            arr[i][j]+=v[i][j]

#공기청정기 위에부분 청소
def clean_up():
    #동쪽부터시작하니 d=0
    d=0
    before=0
    #로봇의 시작부분 다음칸부터 시작
    x, y = machine[0][0],machine[0][1]+1
    
    #로봇이 공기청정기를 만나거나 벽을만나면 방향을 꺾는 조건문 추가
    while True:
        nx = x+dx[d]
        ny = y+dy[d]
        
        if nx == R or ny == C or nx == -1 or ny == -1:
            d = (d-1)%4
            continue
        
        if x == machine[0][0] and y == machine[0][1]:
            break
        
        arr[x][y], before = before, arr[x][y]
        x,y = nx,ny

#공기청정기 아래부분 청소
def clean_down():
    #동쪽부터시작하니 d=0
    d=0
    before=0
    
    #로봇의 시작부분 다음칸부터 시작
    x,y = machine[1][0],machine[1][1]+1
    
    #로봇이 공기청정기를 만나거나 벽을만나면 방향을 꺾는 조건문 추가
    while True:
        nx = x+dx[d]
        ny = y+dy[d]
        
        if nx == R or ny == C or nx == -1 or ny == -1:
            d = (d+1)%4
            continue
            
        if x == machine[1][0] and y ==machine[1][1]:
            break
        
        arr[x][y],before = before,arr[x][y]
        x,y=nx,ny

if __name__=='__main__':
    R,C,T = map(int,s.readline().split())
    arr = [list(map(int,s.readline().split())) for _ in range(R)]
    
    #로봇의 위치 저장하는 배열
    machine=[]
    
    #미세먼지 누적 합 저장
    result=0
    
    #동남서북 4방향
    dx = [0,1,0,-1]
    dy = [1,0,-1,0]

    
    #로봇의 위치찾아서 machine 배열에 저장
    for i in range(R):
        for j in range(C):
            if arr[i][j] == -1:
                machine.append((i,j))
                
    
    #입력받은 T만큼 반복
    for _ in range(T):
        spread()
        clean_up()
        clean_down()
    
    #미세먼지의 양을 찾아서 result에 누적함
    for i in range(R):
        for j in range(C):
            if arr[i][j] != 0 and arr[i][j] != -1:
                result += arr[i][j]
    
    print(result)