문제 이해
위와 같은 격자판에서 숫자가 존재하는 칸은 주변으로 확산된다.
공기청정기의 중간을 기준으로 위는 반시계, 아래는 시계 방향으로 회전한다.
이 두가지 일이 1초에 일어난다.
T초 후에 미세먼지의 총량을 구하시오
문제 접근
문제를 딱 처음보고 지도형태가 나왔기 때문에 BFS로 풀어야 하는 문제인가? 생각했지만 완전탐색문제가 아니기 때문에 다른 방식으로 풀어야겠다고 생각했다.
우선 3가지로 나누었다.
- 미세먼지 확산시키는 함수 (동시에 일어나야 함)
- 공기청정기 돌리는 함수
- 위의 두 함수를 T번 돌리고 미세먼지 총량 출력
이렇게 문제에서 주어진 것만 잘 구현하면 되기 때문에 쉬워보였다.
문제 풀이
미세먼지 확산시키는 함수 (동시에 일어나야 함)
미세먼지를 확산시키는 함수는 아래와 같다.
cur에 현재 미세먼지들의 위치와 크기를 담고 spread함수를 실행하면 각 미세먼지들의 좌표에 dx,dy를 사용하여 상하좌우를 확인한다.
상하좌우에서 확산되지 못하는 조건을 가지지 않을 경우 확산시키고 count를 1 증가하고 곱해서 최종적으로 x,y좌표, 즉, 확산된 주체에서 빼준다.
cur = []
cleaner = []
def spread():
while cur:
x,y,value = cur.pop()
count = 0
for i in range(4):
nx = x+dx[i]
ny = y+dy[i]
if nx<0 or ny<0 or nx>=R or ny>=C:
continue
if (nx,ny) in cleaner:
continue
pan[nx][ny]+=value//5
count+=1
pan[x][y] -= (value//5)*count공기청정기 돌리는 함수
공기청정기는 위, 아래로 나누어서 생각해야했다. 위는 반시계, 아래는 시계 방향이다.
위의 확산 함수와 마찬가지로 dx,dy를 사용했다.
공기청정기의 오른쪽에서 시작하고 각각의 방향에 따라서 index를 조정해준다.
만약 x,y로 이동하다가 벽에 닿는다면 index를 조정하여 방향을 바꿔준다.
swap방식으로 temp에 값을 저장하고 이를 다음 값에 전달하는 형태로 한칸씩 미뤄주었다.
dx = [-1,0,1,0] # 상 우 하 좌
dy = [0,1,0,-1]
def clean(a,b):
# 위에 회전
x, y = a, 1
index = 1 # 우부터 시작 우 상 좌 하
temp = 0 # 공기청정기에서 나오는 바람
while True:
nx = x+dx[index]
ny = y+dy[index]
if nx==R or ny == C or nx==-1 or ny==-1: # 벽에 닿았을 때
index = (index-1)%4
continue
if x==a and y==0: # 공기청정기로 다시 돌아옴
break
pan[x][y], temp = temp, pan[x][y] # swap
x,y = nx, ny
# 아래 회전
x, y = b, 1
index = 1 # 우부터 시작 우 하 좌 상
temp = 0 # 공기청정기에서 나오는 바람
while True:
nx = x+dx[index]
ny = y+dy[index]
if nx==R or ny == C or nx==-1 or ny==-1: # 벽에 닿았을 때
index = (index+1)%4
continue
if x==b and y==0: # 공기청정기로 다시 돌아옴
break
pan[x][y], temp = temp, pan[x][y] # swap
x,y = nx, nyT번 돌리고 미세먼지 총량 출력
cur에 현재 미세먼지의 값을 넣는 모습이다.
T번 반복하고 최종적으로 cur에 value값들을 모두 더한다면 그것이 현재 남아있는 미세먼지의 총량일 것이다!!
for i,line in enumerate(pan):
for j, value in enumerate(line):
if value>0:
cur.append((i,j,value))
if value==-1:
cleaner.append((i,j))
dx = [-1,0,1,0] # 상 우 하 좌
dy = [0,1,0,-1]
a = cleaner[0][0] # 공기청정기의 윗부분
b = cleaner[1][0] # 공기청정기의 아랫부분
for t in range(T):
spread()
clean(a,b)
for i,line in enumerate(pan):
for j, value in enumerate(line):
if value>0:
cur.append((i,j,value))
print(sum(cur[i][2] for i in range(len(cur))))제출 코드
import sys
R,C,T = map(int, sys.stdin.readline().split())
pan = [list(map(int, sys.stdin.readline().split())) for _ in range(R)]
# 미세먼지 확산시키는 함수 동시에 일어나야 함
# 공기청정기 돌리는 함수
# T번 돌리고 미세먼지 총량 출력
cur = []
cleaner = []
def spread():
while cur:
x,y,value = cur.pop()
count = 0
for i in range(4):
nx = x+dx[i]
ny = y+dy[i]
if nx<0 or ny<0 or nx>=R or ny>=C:
continue
if (nx,ny) in cleaner:
continue
pan[nx][ny]+=value//5
count+=1
pan[x][y] -= (value//5)*count
def clean(a,b):
# 위에 회전
x, y = a, 1
index = 1 # 우부터 시작 우 상 좌 하
temp = 0 # 공기청정기에서 나오는 바람
while True:
nx = x+dx[index]
ny = y+dy[index]
if nx==R or ny == C or nx==-1 or ny==-1: # 벽에 닿았을 때
index = (index-1)%4
continue
if x==a and y==0: # 공기청정기로 다시 돌아옴
break
pan[x][y], temp = temp, pan[x][y] # swap
x,y = nx, ny
# 아래 회전
x, y = b, 1
index = 1 # 우부터 시작 우 하 좌 상
temp = 0 # 공기청정기에서 나오는 바람
while True:
nx = x+dx[index]
ny = y+dy[index]
if nx==R or ny == C or nx==-1 or ny==-1: # 벽에 닿았을 때
index = (index+1)%4
continue
if x==b and y==0: # 공기청정기로 다시 돌아옴
break
pan[x][y], temp = temp, pan[x][y] # swap
x,y = nx, ny
for i,line in enumerate(pan):
for j, value in enumerate(line):
if value>0:
cur.append((i,j,value))
if value==-1:
cleaner.append((i,j))
dx = [-1,0,1,0] # 상 우 하 좌
dy = [0,1,0,-1]
a = cleaner[0][0] # 공기청정기의 윗부분
b = cleaner[1][0] # 공기청정기의 아랫부분
for t in range(T):
spread()
clean(a,b)
for i,line in enumerate(pan):
for j, value in enumerate(line):
if value>0:
cur.append((i,j,value))
print(sum(cur[i][2] for i in range(len(cur))))