1. 문제
미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다.
공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r, c)에 있는 미세먼지의 양은 Ar,c이다.
1초 동안 아래 적힌 일이 순서대로 일어난다.
- 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.
- (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
- 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
- 확산되는 양은 A/5이고 소수점은 버린다. 즉, ⌊A/5⌋이다.
- (r, c)에 남은 미세먼지의 양은 A - ⌊A/5⌋×(확산된 방향의 개수) 이다.
r,c
r,c
r,c
r,c
- 공기청정기가 작동한다.
- 공기청정기에서는 바람이 나온다.
- 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
- 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.
- 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.
다음은 확산의 예시이다.
왼쪽과 위쪽에 칸이 없기 때문에, 두 방향으로만 확산이 일어났다.
인접한 네 방향으로 모두 확산이 일어난다.
공기청정기가 있는 칸으로는 확산이 일어나지 않는다.
공기청정기의 바람은 다음과 같은 방향으로 순환한다.
방의 정보가 주어졌을 때, T초가 지난 후 구사과의 방에 남아있는 미세먼지의 양을 구해보자.
입력
첫째 줄에 R, C, T (6 ≤ R, C ≤ 50, 1 ≤ T ≤ 1,000) 가 주어진다.
둘째 줄부터 R개의 줄에 Ar,c (-1 ≤ Ar,c ≤ 1,000)가 주어진다. 공기청정기가 설치된 곳은 Ar,c가 -1이고, 나머지 값은 미세먼지의 양이다. -1은 2번 위아래로 붙어져 있고, 가장 윗 행, 아랫 행과 두 칸이상 떨어져 있다.
출력
첫째 줄에 T초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다.
2. 정답 코드
import sys
input = sys.stdin.readline
r, c, t = map(int, input().split())
graph = []
for _ in range(r):
graph.append(list(map(int, input().split())))
x1, y1, x2, y2 = 0, 0, 0, 0
# 청정기 위치 찾기
for i in range(r):
if graph[i][0] == -1:
x1 = i
x2 = i + 1
break
# 미세먼지 확산
def spread():
path = [(1, 0), (-1, 0), (0, 1), (0, -1)]
tmp = [[0] * c for _ in range(r)]
for i in range(r):
for j in range(c):
if graph[i][j] > 0:
dust = graph[i][j] // 5
cnt = 0
for k in range(4):
nx = i + path[k][0]
ny = j + path[k][1]
if 0 <= nx < r and 0 <= ny < c and graph[nx][ny] != -1:
tmp[nx][ny] += dust
cnt += 1
graph[i][j] -= dust * cnt
for i in range(r):
for j in range(c):
graph[i][j] += tmp[i][j]
# 청정기 돌리기
def clean_up():
path = [(0, 1), (-1, 0), (0, -1), (1, 0)]
index = 0
x, y = x1, 1
before = 0
while True:
if x == x1 and y == 0:
break
nx = x + path[index][0]
ny = y + path[index][1]
if nx < 0 or nx >= r or ny < 0 or ny >= c:
index += 1
continue
graph[x][y], before = before, graph[x][y]
x = nx
y = ny
def clean_down():
path = [(0, 1), (1, 0), (0, -1), (-1, 0)]
index = 0
x, y = x2, 1
before = 0
while True:
if x == x2 and y == 0:
break
nx = x + path[index][0]
ny = y + path[index][1]
if nx < 0 or nx >= r or ny < 0 or ny >= c:
index += 1
continue
graph[x][y], before = before, graph[x][y]
x = nx
y = ny
for _ in range(t):
spread()
clean_up()
clean_down()
print(sum(map(sum, graph)) + 2)3. 생각한 방향 및 설명
구현문제는 엄청나게 어려운 알고리즘 종류가 필요하다기 보단
문제를 진짜 천천히 흐름대로 읽어보는 것이 중요한 것 같다.보통 설명, 그림을 보고 머리속에서 시뮬레이션을 돌려보면 흐름이 보이게 되고, 그 흐름대로 그대로 코드를 쭉 써나가다 보면 어느새 풀려있는 문제가 대다수이다. 시간이 부족하다고 무작정 코드부터 치지말고 충분히 문제를 읽고 생각하고 코드를 써보자.
이 문제도 마찬가지이지만 조건이 조금 많고, 중간중간 한번씩 생각해야 될 것이 있었다.
- 청정기의 위치 찾기
- 미세먼지 확산
- 청정기 돌리기
큰 틀은 이렇게 잡았다.
1. 청정기 위치 찾기
x1, y1, x2, y2 = 0, 0, 0, 0
# 청정기 위치 찾기
for i in range(r):
if graph[i][0] == -1:
x1 = i
x2 = i + 1
break우선 청정기의 위치를 찾아야 → 청정기 돌리기를 위한 로직을 작성할 수 있기 때문이다.
2. 미세먼지 확산
# 미세먼지 확산
def spread():
path = [(1, 0), (-1, 0), (0, 1), (0, -1)]
tmp = [[0] * c for _ in range(r)]
for i in range(r):
for j in range(c):
if graph[i][j] > 0: # 청정기가 아니고, 미세먼지값이 0이 아닐 때
dust = graph[i][j] // 5
cnt = 0
for k in range(4):
nx = i + path[k][0]
ny = j + path[k][1]
if 0 <= nx < r and 0 <= ny < c and graph[nx][ny] != -1:
tmp[nx][ny] += dust
cnt += 1
graph[i][j] -= dust * cnt
for i in range(r):
for j in range(c):
graph[i][j] += tmp[i][j]그 다음 미세먼지 확산로직인데 이 로직은 다른 구현문제들을 풀면서 비슷한 로직을 많이 사용했던 기억이 있어서 그거에 맞춰서 풀었다.
1) 인접한 네 방향으로 확산 → 보통 path리스트를 만들어 반복문을 돌면서 해결
2) 확산은 미세먼지가 있는 모든 칸에서
동시에 일어난다. → 동시에 일어나기 때문에 반복문 순서대로 돌릴경우 동시에 미세먼지 확산을 만드는 것이 아니기 때문에 이를 구현하기 위해 tmp리스트를 하나 더 사용해서 동시성을 유지할 수 있었다.3. 청정기 돌리기
# 청정기 돌리기
def clean_up():
path = [(0, 1), (-1, 0), (0, -1), (1, 0)]
index = 0
x, y = x1, 1
before = 0
while True:
if x == x1 and y == 0:
break
nx = x + path[index][0]
ny = y + path[index][1]
if nx < 0 or nx >= r or ny < 0 or ny >= c:
index += 1
continue
# swap 로직
graph[x][y], before = before, graph[x][y]
x = nx
y = ny마지막으로 청정기 돌리기로직이다. 위, 아래 돌리는 로직은 거의 비슷하다.
우선 x,y 변수를 이용해서 시작점 위치를 설정했다. 여기서 y가 왜 1이냐고 물어볼 수 있는데 그 이유는 0부터 시작하게 되면 -1이라는 청정기의 위치까지 옮겨지기 때문에 1부터 시작해야 맞다. 그리고 before가 0인 이유는 청정기에서 나오는 방향에 있는 칸은 미세먼지가 없기 때문에 0으로 설정하였다.
그리고 python의 swap로직을 이용해서 한칸씩 옮겨주었다.
4. 출력
print(sum(map(sum,graph)) + 2)
최종적으로 전체 미세먼지의 양을 출력하는 코드이다.
sum(map(sum,graph))2차원 리스트의 요소들의 전체 합을 구할 수 있는 코드이다.예를 들어 graph = [[1, 2, 3], [4, 5], [6]]이라 가정하면
map(sum,graph)를 하면 반환되는 값은 [6, 9, 6]이렇게 된다.그리고 sum으로 한번 더 감싸주었기 때문에 전체 요소들의 합을 알 수 있게 된다.
마지막 +2를 이 문제에서 해준 이유는 청정기를 표시하기 위한 -1값 2개까지 더해진 상태이기 때문에 +2를 해서 청정기를 제외해준다.