문제
유난히 추운 날씨가 예상되는 이번 겨울을 대비하기 위해 구사과는 온풍기를 설치하려고 한다. 온풍기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)의 온도를 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다.
구사과의 성능 테스트는 다음과 같은 작업이 순차적으로 이루어지며, 가장 처음에 모든 칸의 온도는 0이다. 문제의 그림에서 빈 칸은 온도가 0인 칸을 의미한다.
- 집에 있는 모든 온풍기에서 바람이 한 번 나옴
- 온도가 조절됨
- 온도가 1 이상인 가장 바깥쪽 칸의 온도가 1씩 감소
- 초콜릿을 하나 먹는다.
- 조사하는 모든 칸의 온도가 K 이상이 되었는지 검사. 모든 칸의 온도가 K이상이면 테스트를 중단하고, 아니면 1부터 다시 시작한다.
집에 있는 모든 온풍기에서 바람이 한 번 나오는 과정을 설명하면 다음과 같다.
<그림 1>
<그림 1>은 크기가 7×8인 집에 온풍기가 (3, 1)에 설치되어 있는 상황이다. 온풍기는 바람이 나오는 방향이 있는데, 그 방향은 오른쪽, 왼쪽, 위, 아래 중 하나이다. 온풍기에서 따뜻한 바람이 한 번 나오면, 다음과 같은 영역의 온도가 칸에 적힌 값만큼 증가하게 된다. 아래 그림은 오른쪽 방향으로 바람이 나온 예시이며, 온풍기에서 바람이 나오는 방향에 따라 <그림 2>를 회전시켜서 해당하는 방향으로 바람이 나왔을 때 증가하는 온도를 구할 수 있다.
<그림 2>
온풍기에서 바람이 한 번 나왔을 때, 온풍기의 바람이 나오는 방향에 있는 칸은 항상 온도가 5도 올라간다. 그 다음 이 바람은 계속 다른 칸으로 이동해 다른 칸의 온도를 위의 그림과 같이 상승시키게 된다. 어떤 칸 (x, y)에 온풍기 바람이 도착해 온도가 k (> 1)만큼 상승했다면, (x-1, y+1), (x, y+1), (x+1, y+1)의 온도도 k-1만큼 상승하게 된다. 이때 그 칸이 존재하지 않는다면, 바람은 이동하지 않는다. 온풍기에서 바람이 한 번 나왔을 때, 어떤 칸에 같은 온풍기에서 나온 바람이 여러 번 도착한다고 해도 온도는 여러번 상승하지 않는다.
<그림 1>의 상태에서 온풍기 바람이 한 번 불었다면, 증가하는 온도의 양은 <그림 3>과 같다.
<그림 3>
일부 칸과 칸 사이에는 벽이 있어 온풍기 바람이 지나갈 수 없다. 바람이 오른쪽으로 불었을 때 어떤 칸 (x, y)에서 (x-1, y+1)로 바람이 이동할 수 있으려면, (x, y)와 (x-1, y) 사이에 벽이 없어야 하고, (x-1, y)와 (x-1, y+1) 사이에도 벽이 없어야 한다. (x, y)에서 (x, y+1)로 바람이 이동할 수 있으려면 (x, y)와 (x, y+1) 사이에 벽이 없어야 한다. 마지막으로 (x, y)에서 (x+1, y+1)로 바람이 이동할 수 있으려면, (x, y)와 (x+1, y), (x+1, y)와 (x+1, y+1) 사이에 벽이 없어야 한다.
예를 들어, (3, 4)와 (3, 5) 사이에 벽이 있는 경우 온풍기에서 바람이 한 번 나왔을 때 온도는 <그림 4>와 같이 상승한다. 벽은 빨간색으로 표시했다.
<그림 4>
(3, 5)는 (3, 4), (2, 4), (4, 4)에서 바람이 이동할 수 없기 때문에, 온도가 상승하지 않는다.
만약 바람의 방향이 왼쪽인 온풍기가 (4, 7)에 있고, (3, 4)와 (3, 5) 사이에 벽, (2, 5)와 (3, 5) 사이에 벽이 있는 경우라면 온풍기에서 바람이 한 번 나왔을 때 <그림 5>와 같이 온도가 상승한다. <그림 6>은 바람의 방향이 아래인 온풍기가 (2, 5)에 있고, (4, 4)와 (4, 5) 사이, (4, 4)와 (5, 4) 사이, (4, 6)과 (5, 6) 사이에 벽이 있는 경우이다.
| <그림 5> | <그림 6> |
구사과의 집에는 온풍기가 2대 이상 있을 수도 있다. 이 경우 각각의 온풍기에 의해서 상승한 온도를 모두 합한 값이 해당 칸의 상승한 온도이다.
예를 들어, <그림 7>은 <그림 6>과 같은 벽을 가지고 있는 집에서 바람이 방향이 위인 온풍기가 (7, 5)에 있는 경우이고, <그림 8>는 <그림 6>과 같은 벽을 가지고 있는 집에서 바람의 방향이 아래인 온풍기가 (2, 5)에 있고, 바람의 방향이 위인 온풍기가 (7, 5)에 있는 경우이다. <그림 8>는 같은 벽을 가지고 있는 집에서 <그림 6>의 온풍기와 <그림 7>의 온풍기가 동시에 설치된 상황이기 때문에, 각 칸의 상승한 온도는 두 그림의 값을 더한 값과 같다. 온풍기가 있는 칸도 다른 온풍기에 의해 온도가 상승할 수 있기 때문에, <그림 8>에서 온풍기의 위치는 표시하지 않았다.
| <그림 7> | <그림 8> |
온도가 조절되는 과정은 다음과 같다.
모든 인접한 칸에 대해서, 온도가 높은 칸에서 낮은 칸으로 ⌊(두 칸의 온도의 차이)/4⌋만큼 온도가 조절된다. 온도가 높은 칸은 이 값만큼 온도가 감소하고, 낮은 칸은 온도가 상승한다. 인접한 두 칸 사이에 벽이 있는 경우에는 온도가 조절되지 않는다. 이 과정은 모든 칸에 대해서 동시에 발생한다.
다음은 온도 조절의 예시이다.
(1, 1)에서 (1, 2)와 (1, 3)으로 공기가 섞인다.
(2, 2)와 (3, 2) 사이에 벽이 있기 때문에, (3, 2)는 온도가 그대로 유지된다.
모든 칸에 대해서 동시에 온도의 조절이 발생한다.
가장 바깥쪽 칸은 1행, R행, 1열, C열에 있는 칸이다. 예를 들어, <그림 9>와 같은 경우 가장 바깥쪽 칸의 온도가 1씩 감소하면 <그림 10>과 같이 된다. 온도가 0인 칸은 온도가 감소하지 않는다.
| <그림 9> | <그림 10> |
방의 크기와 방에 설치된 온풍기의 정보, 벽의 위치와 조사하려고 하는 칸의 위치가 주어진다. 구사과가 먹은 초콜릿의 개수를 출력한다.
입력
첫째 줄에 세 정수 R, C, K가 주어진다. 둘째 줄부터 R개의 줄에 방의 정보가 주어진다. i번째 줄의 j번째 정수는 (i, j)의 정보를 의미하며 다음 중 하나이다.
- 0: 빈 칸
- 1: 방향이 오른쪽인 온풍기가 있음
- 2: 방향이 왼쪽인 온풍기가 있음
- 3: 방향이 위인 온풍기가 있음
- 4: 방향이 아래인 온풍기가 있음
- 5: 온도를 조사해야 하는 칸
다음 줄에는 벽의 개수 W가 주어진다. 다음 W개의 줄에는 벽의 정보가 주어지며, 이 정보는 세 정수 x, y, t로 이루어져 있다. t가 0인 경우 (x, y)와 (x-1, y) 사이에 벽이 있는 것이고, 1인 경우에는 (x, y)와 (x, y+1) 사이에 벽이 있는 것이다.
출력
구사과가 먹는 초콜릿의 개수를 출력한다. 만약, 먹는 초콜릿의 개수가 100을 넘어가면 101을 출력한다.
제한
- 2 ≤ R, C ≤ 20
- 1 ≤ K ≤ 1,000
- 온풍기는 하나 이상 있고, 온도를 조사해야 하는 칸도 하나 이상 있다.
- 0 ≤ W ≤ R×C
- 1 < x ≤ R, 1 ≤ y ≤ C (t = 0)
- 1 ≤ x ≤ R, 1 ≤ y < C (t = 1)
- 온풍기가 있는 칸과 바람이 나오는 방향에 있는 칸 사이에는 벽이 없다.
- 온풍기의 바람이 나오는 방향에 있는 칸은 항상 존재한다.
- 같은 벽이 두 번 이상 주어지는 경우는 없다.
구현해야할 것들을 하나씩 따져보자.
- 온풍기 바람
- 벽
- 온도 조절
- 가장자리 냉각
- 프로그램 종료 조건
본 문제는 순수 구현문제로, 구현해야할 사항이 꽤 있지만 먹은 초콜릿의 개수가 100을 넘어가면 반복문을 종료하고 있으므로 시간제한에 대해 큰 걱정없이 구현 가능하다.
온풍기 바람과 벽
온풍기 바람은 각 칸에서 진행방향이 정해져있고, 하나의 온풍기에서 나온 바람끼리는 같은칸에 중복될 수 없다. 또한 대각선 방향으로 진행될 때는 경로에 놓인 벽의 존재 유무를 따져봐야 하기 때문에, 온풍기의 바람 진행을 벡터를 요소로 담은 리스트로 표현하면 좋을것이란 생각을 할 수 있다. 벽은 이전에 풀었던 문제 (어떤 문제인지는 기억나지 않지만) 처럼 면적을 두배로 한 보드에 대해서 각 좌표를 2배로 맵핑해주고, 그 사이에 벽을 놓는다고 생각하면 편하다. 본 문제에서는 각 칸에서 진행방향에 따라 벽이 놓여있는지를 확인해야하기 때문에 해당 방법이 더욱 유용하다고 볼 수 있다.
온도 조절과 검사
온도 조절 역시 벽의 유무를 신경써야 하지만, 온풍기 바람과 달리 상하좌우 방향만 따지면 되기 때문에 기존 방식을 따라 구현해주면 된다. 프로그램 종료 조건을 따지는것은 데이터를 입력받으면서 미리 '5'의 개수가 몇개인지 세어두지 않았기 때문에, 이중 for 문을 돌며 확인하는 방식으로 구현했다.
결국 온풍기의 바람 진행과 벽을 구현하는게 핵심인 문제였다.
from collections import deque
# 동,서,북,남
dRow = [0,0,0,-1,1]
dCol = [0,1,-1,0,0]
R,C,K = map(int,input().split())
# 1~4:온풍기, 5:조사지역
board = [[9]*(C+1)]
for _ in range(R):
board.append([9] + list(map(int,input().split())))
W = int(input())
walls = [[0]*(2*C+1) for _ in range(2*R+1)]
for _ in range(W):
x,y,t = map(int,input().split())
nx,ny = -1,-1
if t == 0:
nx,ny = 2*x-1,2*y
else:
nx,ny = 2*x,2*y+1
walls[nx][ny] = 1
answer = 0
# 오른쪽, 왼쪽, 위, 아래
heaters = [
[],
[[(-1,0),(0,1)],[(0,1)],[(1,0),(0,1)]],
[[(-1,0),(0,-1)],[(0,-1)],[(1,0),(0,-1)]],
[[(0,-1),(-1,0)],[(-1,0)],[(0,1),(-1,0)]],
[[(0,-1),(1,0)],[(1,0)],[(0,1),(1,0)]]
]
heat_board = [[0]*(C+1) for _ in range(R+1)]
while True:
# 온풍기 가동
for row in range(1,R+1):
for col in range(1,C+1):
if 1 <= board[row][col] <= 4:
visited = [[0]*(C+1) for _ in range(R+1)]
dir = board[row][col]
r,c = row+dRow[dir],col+dCol[dir]
heat_board[r][c] += 5
q = deque()
q.append((r,c,5))
while q:
x,y,h = q.popleft()
nh = h-1
for vectors in heaters[dir]:
nx, ny = x, y
for dx,dy in vectors:
if not (1 <= nx+dx <= R and 1 <= ny+dy <= C) or\
walls[2*nx+dx][2*ny+dy] == 1:
break
nx += dx
ny += dy
else:
if nh > 0 and visited[nx][ny] == 0:
visited[nx][ny] = 1
heat_board[nx][ny] += nh
q.append((nx,ny,nh))
# 온도 조절
new_heat = [[*elem] for elem in heat_board]
for row in range(1,R+1):
for col in range(1,C+1):
if heat_board[row][col] >= 4:
for i in range(1,5):
nRow,nCol = row+dRow[i],col+dCol[i]
if 1 <= nRow <= R and 1 <= nCol <= C\
and heat_board[nRow][nCol] < heat_board[row][col]\
and walls[2*row+dRow[i]][2*col+dCol[i]] == 0:
delta = (heat_board[row][col] - heat_board[nRow][nCol]) // 4
new_heat[nRow][nCol] += delta
new_heat[row][col] -= delta
# 가장자리 냉각
for row in range(2,R):
new_heat[row][1] -= 1 if new_heat[row][1] > 0 else 0
new_heat[row][C] -= 1 if new_heat[row][C] > 0 else 0
for col in range(1,C+1):
new_heat[1][col] -= 1 if new_heat[1][col] > 0 else 0
new_heat[R][col] -= 1 if new_heat[R][col] > 0 else 0
# 초콜릿 까먹기
answer += 1
# 검사
targets,cnt = 0,0
for row in range(1,R+1):
for col in range(1,C+1):
if board[row][col] == 5:
targets += 1
if new_heat[row][col] >= K:
cnt += 1
if targets == cnt:
print(answer)
break
if answer > 100:
print(101)
break
heat_board = [[*elem] for elem in new_heat]'PS > 백준' 카테고리의 다른 글
| 21611번 - 마법사 상어와 블리자드 (1) | 2022.10.01 |
|---|---|
| 21610번 - 마법사 상어와 비바라기 (1) | 2022.09.30 |
| 20058번 - 마법사 상어와 파이어스톰 (0) | 2022.09.29 |
| 20057번 - 마법사 상어와 토네이도 (1) | 2022.09.29 |
| 23288번 - 주사위 굴리기 2 (0) | 2022.09.28 |