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())