[Python] 백준 17144번: 미세먼지 안녕! - simulation (삼성 기출)

문제

17144번: 미세먼지 안녕!

풀이

시뮬레이션 문제라 복잡한 스킬이 필요하지는 않았지만 공기청정기를 위/아래로 나눠서 순환하는 부분을 짜는게 헷갈렸다.

 

테스트케이스도 다 맞고 질문게시판의 반례들도 다 맞는데 틀렸습니다가 떠서 그냥 자러갈까 생각했지만 옆에 그림을 그려놓고 범위를 다 적어둔 다음 코드를 차근차근 보니 범위를 하나 잘못설정한게 있었다. 애초에 표랑 범위를 그려놓고 짜는게 더 효율적일것 같다는 교훈  

 

python3으로 제출하니 시간초과가 나서 pypy3으로 제출함 

 

import sys

# 세로, 가로, 초(반복 횟수)
R, C, T = map(int, sys.stdin.readline().split(" "))

dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]

# 인풋으로 들어오는 배열 채우기
field = []
for _ in range(R):
    field.append(list(map(int, sys.stdin.readline().split(" "))))


# 공기청정기 찾기
now = (0, 0)
for i in range(R):
    if field[i][0] == -1 and field[i+1][0] == -1:
        now = (i, i+1)
        break


# T번 반복
for _ in range(T):

    # 확산
    new = [[0 for _ in range(C)] for _ in range(R)]

    for i in range(R):
        for j in range(C):

            # 미세먼지가 5 이상이어야 유의미한 계산 가능 
            if field[i][j] >= 5:

                # 주변에 나눠줄 애들 
                each = field[i][j] // 5
                
                # 주변에 나눠준 횟수 카운팅 위함
                count = 0

                # 사방 탐색
                for k in range(4):
                    
                    ndr = i + dr[k]
                    ndc = j + dc[k]

                    # 범위 안에 들어오고, 공기청정기의 자리가 아닌 경우
                    if 0 <= ndr < R and 0 <= ndc < C and field[ndr][ndc] != -1:
                        
                        # 카운트를 1 늘려주고
                        count += 1
                        
                        # 새 배열에 미세먼지를 받은만큼 더해줌
                        new[ndr][ndc] += each
                
                # 나눠준 애 업데이트 (나눠준만큼 빼기)
                field[i][j] = field[i][j] - count * each

    # 두 배열 값 합치기 
    for i in range(R):
        for j in range(C):
            field[i][j] += new[i][j]



    # 순환
    # upper bound (오 위 왼 아래 순서)
    temp = field[now[0]][C-1]
    for i in range(C-2, 0, -1):
        field[now[0]][i+1] = field[now[0]][i]

    temp2 = field[0][C-1]
    for i in range(now[0]-1):
        field[i][C-1] = field[i+1][C-1]
    field[now[0]-1][C-1] = temp

    temp = field[0][0]
    for i in range(C-1):
        field[0][i] = field[0][i+1]
    field[0][C-2] = temp2

    for i in range(now[0]-1, 1, -1):
        field[i][0] = field[i-1][0]
    field[now[0]][1] = 0
    field[1][0] = temp



    # lower boud (오 아래 왼 위 순서)
    temp = field[now[1]][C-1]
    for i in range(C-2, 0, -1):
        field[now[1]][i+1] = field[now[1]][i]

    temp2 = field[R-1][C-1]
    for i in range(R-1, now[1], -1):
        field[i][C - 1] = field[i-1][C - 1]
    field[now[1]+1][C-1] = temp

    temp = field[R-1][0]
    for i in range(C-1):
        field[R-1][i] = field[R-1][i+1]
    field[R-1][C-2] = temp2

    for i in range(now[1]+1, R-1):
        field[i][0] = field[i+1][0]
    field[now[1]][1] = 0
    field[R-2][0] = temp


# 남은 미세먼지 수 계산
s = 0
for each in field:
    s += sum(each)

# 공기청정기 2칸을 각각  -1로 표현했으니 최종값에 2를 더해줌 
print(s+2)