🔴 문제 개요
🚀 난이도 GOLD 4
주어진 matrix의 공기청정기의 위치와 미세먼지 양이 주어졌을 때 조건에 따라 T초동안 미세먼지 확산 - 공기청정기 정화를 수행한 결과를 구하면 되는 문제
확산 - 공기청정기 정화 과정
공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r, c)에 있는 미세먼지의 양은 이다.
1초 동안 아래 적힌 일이 순서대로 일어난다.
- 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.
- (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
- 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
- 확산되는 양은 이고 소수점은 버린다.
- (r, c)에 남은 미세먼지의 양은 - (ㅇ\/5)×(확산된 방향의 개수) 이다.
- 공기청정기가 작동한다.
- 공기청정기에서는 바람이 나온다.
- 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
- 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.
- 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.
🟠 Solution
입력 제한도 많이 작아서 부담 없이 시뮬레이션 문제로 생각하고 풀이해도 좋을 것 같습니다.
우선 전체적인 코드 뼈대와 입력부를 정의합니다.
import sys
input = sys.stdin.readline
R, C, T = map(int, input().rstrip().split())
air_conditioner = None # 공기청정기 위치를 담을 변수
matrix = []
for r in range(R):
row = input().rstrip().split()
if not air_conditioner and row[0] == "-1":
air_conditioner = (r, r + 1) # 공기청정기는 첫 번째 열의 연속된 행에 위치
matrix.append(list(map(int, row)))
def diffusion() -> None:
"""
matrix에 1초동안 확산한 결과를 적용한다.
"""
pass
def cleaning() -> None:
"""
1초동안 공기청정기가 정화한 결과를 적용한다.
"""
pass
for _ in range(T):
diffusion()
cleaning()
matrix[air_conditioner[0]][0] = 0
matrix[air_conditioner[1]][0] = 0
print(sum(map(sum, matrix)))
matrix를 입력받으면서 공기청정기(air_conditioner)의 위치를 알아두어야합니다. 공기청정기는 첫 번째 열의 연속된 행에 위치하므로 (r, r+1)과 같이 저장해둡니다.
확산-공기청정기 정화 연산을 해주는 메서드를 정의하고 이를 T초 동안 반복해서 수행한 뒤, -1로 표시되어있는 공기청정기의 위치의 값을 0으로 바꿔줍니다. 그리고 2차원 matrix의 합을 구해서 출력하면 됩니다. 2차원 리스트 값의 총 합은 sum(map(sum, matrix))와 같이 구할 수 있습니다.
먼저 확산 연산에 해당하는 메서드를 구현해보겠습니다.
dy = [-1, 1, 0, 0] # 상, 하, 좌, 우 탐색 시 사용
dx = [0, 0, -1, 1]
def diffusion() -> None:
"""
matrix에 1초동안 확산한 결과를 적용한다.
"""
# 확산 이후 변화량을 담을 matrix
add_matrix = [[0 for _ in range(C)] for _ in range(R)]
for y in range(R):
for x in range(C):
if matrix[y][x] > 0:
cnt = 0
cur_dust = matrix[y][x]
for d in range(4):
ny = y + dy[d]
nx = x + dx[d]
# 유효한 좌표 중 공기청정기가 아닌 곳으로 확산
if 0 <= ny < R and 0 <= nx < C and matrix[ny][nx] != -1:
cnt += 1
# 확산양을 바로 더해주지 않고 따로 저장
add_matrix[ny][nx] += cur_dust // 5
# 확산 후 줄어들어야 하는 양
add_matrix[y][x] -= cur_dust // 5 * cnt
# 확산 이후 변화량을 원래 matrix에 더해주기
for y in range(R):
for x in range(C):
matrix[y][x] += add_matrix[y][x]matrix를 순회하며, 미세먼지가 있는 곳은 4방향으로 조건에 맞게 확산하도록 합니다. 이때 주의할 점은 순회하면서 바로 matrix를 업데이트 하면 이는 다음 좌표의 확산에 영향을 주게 됩니다. 모든 확산은 동시에 일어나므로, 별도의 matrix(add_matrix)에 확산 이후의 변화량을 따로 저장해두고, 한 번 matrix 순회가 끝나면 한 번에 matrix를 업데이트하도록 해야합니다.
다음은 공기청정기의 정화 연산에 해당하는 메서드를 구현해보겠습니다.
def cleaning() -> None:
"""
1초동안 공기청정기가 정화한 결과를 적용한다.
"""
# 공기청정기 위쪽
# 왼쪽 맨 위 -> 공기 청정기
r = air_conditioner[0] - 1
while r - 1 >= 0:
matrix[r][0] = matrix[r - 1][0]
r -= 1
# 오른쪽 맨 위 -> 왼쪽 맨 위
c = 0
while c + 1 < C:
matrix[0][c] = matrix[0][c + 1]
c += 1
# 오른쪽 아래 -> 오른쪽 위
while r + 1 <= air_conditioner[0]:
matrix[r][-1] = matrix[r + 1][-1]
r += 1
# 공기청정기 -> 오른쪽 아래
while c - 1 > 0:
matrix[r][c] = matrix[r][c - 1]
c -= 1
# 공기청정기에서 먼지 정화
matrix[r][0] = -1
matrix[r][1] = 0
# 공기청정기 아래쪽
# 왼쪽 맨 아래 -> 공기청정기
r = air_conditioner[1] + 1
while r + 1 < R:
matrix[r][0] = matrix[r + 1][0]
r += 1
# 오른쪽 맨 아래 -> 왼쪽 맨 아래
c = 0
while c + 1 < C:
matrix[-1][c] = matrix[-1][c + 1]
c += 1
# 오른쪽 위 -> 오른쪽 맨 아래
while r - 1 >= air_conditioner[1]:
matrix[r][-1] = matrix[r - 1][-1]
r -= 1
# 공기청정기 -> 오른쪽 위
while c - 1 > 0:
matrix[r][c] = matrix[r][c - 1]
c -= 1
# 공기청정기에서 먼지 정화
matrix[r][0] = -1
matrix[r][1] = 0위쪽 공기청정기, 아래쪽 공기청정기를 따로 두었고, 각각 절차적으로 공기가 이동하는 방향에 따라 그대로 구현했습니다. 조금 복잡한 감이 없지 않아 있지만, 문제에서 제시된 아래의 그림을 그대로 따라 구현하면 어렵지 않게 구현할 수 있습니다.
이 연산의 구현 팁은 먼저 없어지는 좌표를 이전 좌표가 채우는 방식으로 구현하면 생각하기 쉽습니다. 예를 들어 위 그림에 해당하는 예시의 경우 위쪽 공기청정기는 (2,0)의 미세먼지가 사라지고, 아래쪽은 (5,0)의 미세먼지가 사라지니 각각 이를 (1,0), (6,0)이 채우는 방향으로 순서대로 구현하면 됩니다.
🟡 후기
역시 시뮬레이션 문제는 코드의 뼈대를 세워놓고 절차적으로 메서드를 구현해나가는 방식으로 풀이하는 것이 좋은 것 같습니다. 문제의 조건이 비교적 간단하기도 했지만, 점점 시뮬레이션 문제를 풀이하는 시간이 줄어들고 있는 것 같아 좋네요!
🙏 문제 접근 방법 및 코드에 대한 피드백과 질문은 환영입니다!
