문제 바로가기
문제:
미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다. 공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r, c)에 있는 미세먼지의 양은 Ar,c이다. 1초 동안 아래 적힌 일이 순서대로 일어난다. 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다. (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다. 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다. 확산되는 양은 Ar,c/5이고 소수점은 버린다. 즉, ⌊Ar,c/5⌋이다. (r, c)에 남은 미세먼지의 양은 Ar,c - ⌊Ar,c/5⌋×(확산된 방향의 개수) 이다. 공기청정기가 작동한다. 공기청정기에서는 바람이 나온다. 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다. 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다. 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.
자세한 문제는 링크로 첨부한다.
https://www.acmicpc.net/problem/17144
입력:
첫째 줄에 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초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다.
풀이:
골드 4 문제인데 정답률이 50프로나 된다.
조금 당황스럽다 문제 읽었는데 bfs를 사용한 시뮬레이션이다.
바이러스 확산인 bfs와
바람이 위로 가는 공기청정기 와 바람이 아래로 가는 공기청정기를 구현해주면 된다.
import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
r, c, t = map(int, sys.stdin.readline().split())
map = [list(map(int, sys.stdin.readline().rstrip().split(" "))) for _ in range(r)]
move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
down_air, up_air = 1e9, 1e9
# 공기청정기 위치 확인
for i in range(r):
if map[i][0] == -1:
up_air = i
down_air = i + 1
break
# 미세먼지 확장
def bfs():
# 얼만큼 바뀌는제 배열 선언
arr = [[0] * c for _ in range(r)]
for x in range(r):
for y in range(c):
if map[x][y] != 0 and map[x][y] != -1:
temp = 0
for dx, dy in move:
nx = dx + x
ny = dy + y
# 확산 가능
if 0 <= nx < r and 0 <= ny < c and map[nx][ny] != -1:
# 확산된 바이러스 배열 저장
arr[nx][ny] += map[x][y] // 5
# 빠진 바이러스 저장
temp += map[x][y] // 5
# 깎여나간거 반영
map[x][y] -= temp
# 바뀐거 반영
for i in range(r):
for j in range(c):
map[i][j] += arr[i][j]
def up():
# 우 상 좌 하
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]
# 이전
temp = 0
# 방향
dir = 0
# 시작 좌표
x, y = up_air, 1
while True:
nx = x + dx[dir]
ny = y + dy[dir]
# 한바퀴 돎
if x == up_air and y == 0:
break
# 방향 전환
if nx < 0 or nx >= r or ny < 0 or ny >= c:
dir += 1
continue
# 한칸씩 옮겨주기 바꿔주기
map[x][y], temp = temp, map[x][y]
x = nx
y = ny
def down():
# 우 하 좌 상
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
# 시작 좌표
x, y = down_air, 1
dir = 0
temp = 0
while True:
nx = x + dx[dir]
ny = y + dy[dir]
# 한바퀴 돎
if x == down_air and y == 0:
break
# 방향 전환
if nx < 0 or nx >= r or ny < 0 or ny >= c:
dir += 1
continue
# 한칸씩 옮겨주기 바꿔주기
map[x][y], temp = temp, map[x][y]
x = nx
y = ny
for _ in range(t):
bfs()
up()
down()
print(sum([sum(i) for i in map]) + 2)
Up함수와 down함수에서 1바퀴를 한 번에 돈다
Up함수를 예를들면
dx,dy 방향을 미리 정해둔다 오른쪽 위쪽 왼쪽 아래쪽 이렇게 그리고 범위가 벗어나게 되면 direction 을 1 추가해 방향을 바꿔준다.
계속 앞으로 가면서 이전꺼를 기억해두고, 한칸씩 밀어준다. 만약에 돌아오게 되면 break하면된다.
마지막에 +2 해준 이유는 공기청정기가 -1 2개 있어서 총 합에서 -2가 빠져나가게 된다.
댓글