[백준] 17144번 미세먼지 안녕! _ 문제 풀이

 


1. 문제

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

2. 풀이

2.1. 내 풀이

삼성 SW 역량테스트 문제입니다. 아래와 같은 풀이를 통하여 문제를 해결했습니다. python으로 제출하면 시간초과가 발생하고 pypy3로 제출하면 시간초과가 발생하지 않습니다. 아래와 같은 문제들로 시간을 많이 잡아 먹었습니다.

  • map 을 복사할 때, 공기청정기의 좌표도 복사하지 않아 문제가 발생했습니다.
  • 공기 청정기의 동작에서 횟수 1번이 틀려 테스트케이스는 다 맞았지만, 제출시 ‘틀렸습니다’가 떴습니다.
R, C, T = map(int, input().split())
map = [ list(map(int, input().split())) for _ in range(R)]
# 상우하좌
n_r = [-1, 0, 1, 0]
n_c = [0, 1, 0, -1]
# 청소기 찾기
cleaner_r = 0
for r_idx in range(R):
    if map[r_idx][0] == -1:
        cleaner_r = r_idx
        break

def count_dust():
    dust = 2
    for i in range(R):
        dust += sum(map[i])
    return dust

# 확산
def spread():
    global map
    map_copy = [ [0]*C for _ in range(R) ]
    map_copy[cleaner_r][0] = map_copy[cleaner_r+1][0] = -1
    for r_idx in range(R):
        for c_idx in range(C):
            # 공기 청정기면 넘어감
            if map[r_idx][c_idx] == -1:
                continue
            # 4방향 살펴보기
            spread_way = 0
            for i in range(4):
                # 범위 벗어나면 무시
                if (r_idx + n_r[i] < 0) or (r_idx + n_r[i] >= R) or (c_idx + n_c[i] < 0) or (c_idx + n_c[i] >= C):
                    continue
                # 공기 청정기이면 무시
                if map[r_idx + n_r[i]][c_idx + n_c[i]] == -1:
                    continue
                map_copy[r_idx + n_r[i]][c_idx + n_c[i]] += (map[r_idx][c_idx] // 5)
                spread_way += 1
            map_copy[r_idx][c_idx] += (map[r_idx][c_idx] - spread_way * (map[r_idx][c_idx] // 5))
    map = map_copy

# 공기청정기 동작
def clean():
    # 반시게방향
    for r_idx in range(cleaner_r-2, -1, -1):    # 공기청정기 row 좌표 - 1 번
        map[r_idx+1][0] = map[r_idx][0]
    for c_idx in range(1, C):                   # C-1 번 
        map[0][c_idx-1] = map[0][c_idx]
    for r_idx in range(1, cleaner_r+1):         # 공기청정기 row 좌표 번
        map[r_idx-1][C-1] = map[r_idx][C-1]
    for c_idx in range(C-2, 0, -1):             # C-2 번
        map[cleaner_r][c_idx+1] = map[cleaner_r][c_idx]
    map[cleaner_r][1] = 0

    # 시계방향
    for r_idx in range(cleaner_r+3, R):         # R - (공기청정기 row 좌표 + 2) - 1
        map[r_idx-1][0] = map[r_idx][0]
    for c_idx in range(1, C):                   # C-1 번
        map[R-1][c_idx-1] = map[R-1][c_idx]
    for r_idx in range(R-2, cleaner_r, -1):     # R - (공기청정기 row 좌표 + 2)
        map[r_idx+1][C-1] = map[r_idx][C-1]
    for c_idx in range(C-2, 0, -1):             # C-2 번
        map[cleaner_r+1][c_idx+1] = map[cleaner_r+1][c_idx]
    map[cleaner_r + 1][1] = 0

for _ in range(T):
    spread()
    clean()
print(count_dust())