[python] 백준 - 17144. 미세먼지 안녕!(삼성 SW 역량 테스트 기출 문제)

문제 해결

1. 먼지를 동시에 확산시킨다.

 (1) 똑같은 크기의 0으로 채워진 임시 2중 배열을 만든다.

 (2) 확산시킬 양만큼 임시 배열에 더해준다. ( 그렇게 하면서 확산시킨양만큼 원래의 배열에서 빼준다. )

 (3) 확산이 모두 완료되면 임시배열에 있는 값을 원래 배열에 더해준다.

2. 공기청정기 | 먼지를 빨아들이는 방향으로 생각해보자.

 (1) 공기청정기에서 화살표의 역방향으로 차근차근 이동한다.

 (2) 이동하면서 다음위치에 먼지가 있으면 현재위치에 덮어씌워준다.

 

-> 처음에 먼지를 확산시킬 때 기존의 먼지가 있는 곳은 확산이 안된다고 혼자 착각을 해서 문제를 이해하는데 많은 시간이 걸렸다. (이웃님이 명쾌하게 알려줘서 금방 해결!)

-> 공기청정기가 자기 자신으로 돌아올수 있도록  x의 탐색 범위를 설정해줘야 한다. ( 위쪽은 위쪽 구역만큼, 아래쪽은 아래쪽 구역만큼 )

 

+ 역시 python 으로 하니 시간초과가 나왔다. pypy 제출해서 통과.

소스 코드

def air_purifier():
    # 공기청정기가 바람을 흡수하는 방향으로 진행, 먼지를 한칸 씩 당겨준다.
    for i in range(2):
        x, y = machine[i][0], machine[i][1]
        cx, cy = x, y
        k = 0

        # 위쪽 공기청정기
        if i == 0:
            cx -= 1
            dx, dy = [-1, 0, 1, 0], [0, 1, 0, -1]  # 위, 오, 아, 왼 | 시계방향
            while k != 4:
                nx = cx + dx[k]
                ny = cy + dy[k]
                if 0 <= nx <= x and 0 <= ny < C:  # nx가 만족하는 범위는 공기청정기와 벽 사이
                    if home[nx][ny] != -1:
                        home[cx][cy] = home[nx][ny]
                    else:
                        home[cx][cy] = 0  # 마지막 공기청정기를 만났을 때
                    cx, cy = nx, ny
                else:
                    k += 1

        # 아래쪽 공기청정기
        else:
            cx += 1
            dx, dy = [1, 0, -1, 0], [0, 1, 0, -1]  # 아, 오, 위, 왼 | 반시계방향
            while k != 4:
                nx = cx + dx[k]
                ny = cy + dy[k]
                if x <= nx < R and 0 <= ny < C:
                    if home[nx][ny] != -1:
                        home[cx][cy] = home[nx][ny]
                    else:
                        home[cx][cy] = 0
                    cx, cy = nx, ny
                else:
                    k += 1

    return


def dust_diffusion():
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
    tmp_home = [[0]*C for _ in range(R)]  # 비어있는 임시 home 2중 배열을 만든다.
    for i in range(R):
        for j in range(C):
            if home[i][j] > 0:
                cnt = 0  # 확산된 방의 갯수만큼 빼줘야 되기 때문에 cnt를 세준다.
                for k in range(4):  # 현 위치에서 4방향 탐색
                    nx = i + dx[k]
                    ny = j + dy[k]
                    if 0 <= nx < R and 0 <= ny < C:
                        if home[nx][ny] != -1:
                            # 벽이 아니고, 공기청정기도 아니라면 확산
                            dif_dust = home[i][j]//5
                            tmp_home[nx][ny] += dif_dust
                            cnt += 1

                home[i][j] -= dif_dust*cnt

    # home의 먼지 양에 환산된 tmp_home의 먼지 양을 더해준다.
    for i in range(R):
        for j in range(C):
            if tmp_home[i][j] > 0:
                home[i][j] += tmp_home[i][j]

    return


R, C, T = map(int, input().split())  # 행, 열, 시간
home = [list(map(int, input().split())) for _ in range(R)]

# 공기청정기의 위치, 이 문제에서는 항상 왼쪽 벽에 붙어있다고 가정하는 것 같다.
machine = []
for i in range(R):
    for j in range(C):
        if home[i][j] == -1:
            machine.append([i, j])

for _ in range(T):
    dust_diffusion()
    air_purifier()

result = 0
for i in home:
    result += sum(i)

print(result+2)

 

 

출처 : BACKJOON ONLINE JUDGE

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

17144번: 미세먼지 안녕!