[백준] 17144번: 미세먼지 안녕! (골드4, 파이썬)

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

17144번: 미세먼지 안녕!

 

아이디어

구현 문제이다.

• 먼지는 동시에 확산되기 때문에 모든 먼지 좌표를 먼저 큐에 넣고, 그 후 확산 값을 계산해서 업데이트 해주었다. 
• 공기청정기가 작동하는 부분은 방향 벡터와 무한 반복문을 사용해서 구현했다. 공기청정기를 기준으로 상하로 나누고, 각 좌표를 현재 방향(d)으로 이동하면서 더이상 이동할 수 없으면 방향 벡터를 시계/반시계 방향으로 회전한 뒤 다시 전진하는 코드를 작성했다.

아래는 문제를 풀기 전 스케치한 내용이다.

BFS(): 먼지 확산 시키기

우선 현재 맵에 있는 모든 먼지 좌표가 필요했다. 그래서 아래와 같은 메서드를 만들어 사용했다.

def getDustPos():
    dusts = []
    for i in range(R):
        for j in range(C):
            if board[i][j] > 0:
                dusts.append((i,j, board[i][j]))
    
    return dusts

구한 먼지들을 큐에 넣고 반복을 시작하였다. 탐색을 하지 않기 때문에 bfs라고 부르면 안되지만, 구조가 닮았기 때문에 메서드명을 bfs라고 했다...

def bfs(R, C):
    global board
    queue = deque(getDustPos())

    while queue:
        x, y, v = queue.popleft()

        cnt = 0
        tmp = v // 5
        for d in dv:
            nx = x + d[0]
            ny = y + d[1]

            if nx < 0 or nx >= R or ny < 0 or ny >= C or board[nx][ny] == -1:
                continue
            
            board[nx][ny] += tmp
            cnt += 1
        
        board[x][y] -= tmp * cnt

코드에서 먼지의 좌표 외에 먼지의 값(v)을 저장하는 이유는, 확산의 영향을 받은 값을 사용할 수 없기 때문이다. 초기의 값으로 확산시켜준다.

 

up_cleaner(), down_cleaner(): 공기청정기 작동

스케치대로 방향을 사용하였다.

 

우선 방향에 맞게 벡터 리스트를 만들어준 뒤, 

dv = [(-1, 0), (0,1), (1,0), (0,-1)]

 

공기청정기를 기준으로 위쪽, 아래쪽으로 나누어서 구해주었다.

def up_cleaner(x, y):
    global board
    v, d = 0, 1
    while True:

        nx = x + dv[d][0]
        ny = y + dv[d][1]

        if nx < 0 or nx >= R or ny < 0 or ny >= C:
            d = (d + 3) % 4     # 반시계 방향으로 회전
            continue

        else:
            if board[nx][ny] == -1: # 이동한 곳이 공청기라면
                return
            
            tmp = board[nx][ny] # 현재 위치의 값 저장
            board[nx][ny] = v     # 이전 위치값 변경
            v = tmp             # 현재 위치에 원래 있던 값으로 업데이트
            x, y = nx, ny

v 는 바뀔 값, d는 방향이다.

down에서 바뀌는 부분은 진행하다 board의 끝에 다다랐을 때이다. 

up에서는 아래와 같이 반시계 방향으로 회전시키고,

        if nx < 0 or nx >= R or ny < 0 or ny >= C:
            d = (d + 3) % 4     # 반시계 방향으로 회전
            continue

 

down에서는 시계 방향으로 회전시킨다.

        if nx < 0 or nx >= R or ny < 0 or ny >= C:
            d = (d + 1) % 4     # 시계 방향으로 회전
            continue

 

전체 코드

# 3:37 ~ 5:08 (1'31")

from collections import deque

dv = [(-1, 0), (0,1), (1,0), (0,-1)]
R, C, T = map(int, input().split())

board = [[int(x) for x in input().split()] for _ in range(R)]


def getDustPos():
    dusts = []
    for i in range(R):
        for j in range(C):
            if board[i][j] > 0:
                dusts.append((i,j, board[i][j]))
    
    return dusts

def getCleanerPos():
    for i in range(R):
        if board[i][0] == -1:
            return i

def getAllDusts():
    total = 0
    for i in range(R):
        for j in range(C):
            if board[i][j] > 0:
                total += board[i][j]
    return total

def bfs(R, C):
    global board
    queue = deque(getDustPos())

    while queue:
        x, y, v = queue.popleft()

        cnt = 0
        tmp = v // 5
        for d in dv:
            nx = x + d[0]
            ny = y + d[1]

            if nx < 0 or nx >= R or ny < 0 or ny >= C or board[nx][ny] == -1:
                continue
            
            board[nx][ny] += tmp
            cnt += 1
        
        board[x][y] -= tmp * cnt

def up_cleaner(x, y):
    global board
    v, d = 0, 1
    while True:

        nx = x + dv[d][0]
        ny = y + dv[d][1]

        if nx < 0 or nx >= R or ny < 0 or ny >= C:
            d = (d + 3) % 4     # 반시계 방향으로 회전
            continue

        else:
            if board[nx][ny] == -1: # 이동한 곳이 공청기라면
                return
            
            tmp = board[nx][ny] # 현재 위치의 값 저장
            board[nx][ny] = v     # 이전 위치값 변경
            v = tmp             # 현재 위치에 원래 있던 값으로 업데이트
            x, y = nx, ny

def down_cleaner(x, y):
    global board
    v, d = 0, 1
    while True:

        nx = x + dv[d][0]
        ny = y + dv[d][1]

        if nx < 0 or nx >= R or ny < 0 or ny >= C:
            d = (d + 1) % 4     # 시계 방향으로 회전
            continue

        else:
            if board[nx][ny] == -1:
                return
            tmp = board[nx][ny] # 현재 위치의 값 저장
            board[nx][ny] = v     # 이전 위치값 변경
            v = tmp             # 현재 위치에 원래 있던 값으로 업데이트
            x, y = nx, ny


cleaner_x = getCleanerPos() # 위 공청기 x좌표, y좌표

for i in range(T):

    bfs(R, C) # 먼지 동시 확산

    up_cleaner(cleaner_x, 0)
    down_cleaner(cleaner_x + 1, 0)

print(getAllDusts())

 

오랜만에 풀이 코드가 깔끔해서 좋다 ㅎㅎㅎ!!