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

'삼성 SW 역량 테스트' 기출 문제 입니다. 😀
문제 👉 17144번: 미세먼지 안녕!

1. 문제

1. R*C 크기의 격자판에서 공기청정기는 항상 1번 열에 2칸을 차지하고, 나머지 칸에는 미세먼지의 양이 나타난다.
2. 1초 동안 아래 적힌 일이 순서대로 일어난다.
   1. 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.
      • (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
      • 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
      • 확산되는 양은 A_r,c/5이고 소수점은 버린다.
      • (r, c)에 남은 미세먼지의 양은 A_r,c - (A_r,c/5)×(확산된 방향의 개수) 이다.
   2. 공기청정기가 작동한다.
      • 공기청정기에서는 바람이 나온다.
      • 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
      • 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.
      • 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.

2. 풀이

시뮬레이션를 이용한 문제 풀이

1. 미세먼지가 확산하는 함수를 작성한다.
2. 공기청정기가 청소하는 함수를 작성한다.

3. 코드

def solution():
    def spread(): #확산
        move = [[0] * C for _ in range(R)]
        for i in range(R):
            for j in range(C):
                if board[i][j] >= 5:
                    d = board[i][j]//5
                    for dx, dy in (-1,0), (1,0), (0,1), (0,-1):
                        ni, nj = i+dx, j+dy
                        if 0 <= ni < R and 0 <= nj < C and board[ni][nj] != -1:
                            move[ni][nj] += d
                            board[i][j] -= d
        for i in range(R):
            for j in range(C):
                board[i][j] += move[i][j]

    def cleanAir(start, dir): # 시작행, dir-방향 -1:위, 1:아래
        if dir == -1:
            for i in range(start - 1, 0, -1):   # 위로
                board[i][0]= board[i - 1][0]
            for j in range(0, C - 1):           # 오른쪽으로
                board[0][j] = board[0][j + 1]
            for i in range(0, start):           # 아래로
                board[i][C - 1] = board[i + 1][C - 1]
            for j in range(C - 1, 1, -1):       # 왼쪽으로
                board[start][j] = board[start][j - 1]
        else:
            for i in range(start + 1, R - 1):
                board[i][0] = board[i + 1][0]
            for j in range(0, C - 1):
                board[R - 1][j] = board[R - 1][j + 1]
            for i in range(R - 1, start, -1):
                board[i][C - 1] = board[i - 1][C - 1]
            for j in range(C - 1, 1, -1):
                board[start][j] = board[start][j - 1]
        board[start][1] = 0

    R, C, T = map(int, input().split()) # R:행, C:열, T:초
    board = [list(map(int, input().split())) for _ in range(R)]
    cleaner = [] # 공기청정기
    for i in range(R):
        if board[i][0] == -1:
            cleaner.append(i)
            cleaner.append(i + 1)
            break

    for _ in range(T): # T초 동안
        spread()
        cleanAir(cleaner[0], -1) # 반시계방향
        cleanAir(cleaner[1], 1) # 시계방향

    print(sum(map(sum, board))+2)

solution()

• 결과 : 4440 ms
• 이 문제는 최적화를 잘 안하면 시간 초과가 나기 쉽다... 코드는 쉬운데 상당히 까다로운 문제다...

---

References

•  

---

🏋🏻 개인적으로 공부한 내용을 기록하고 있습니다.
잘못된 부분이 있다면 과감하게 지적해주세요!! 🏋