JB의 이모저모
[BOJ 23289 Platinum 5] 온풍기 안녕!(Python) 본문
https://www.acmicpc.net/problem/23289
23289번: 온풍기 안녕!
유난히 추운 날씨가 예상되는 이번 겨울을 대비하기 위해 구사과는 온풍기를 설치하려고 한다. 온풍기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기
www.acmicpc.net
문제
유난히 추운 날씨가 예상되는 이번 겨울을 대비하기 위해 구사과는 온풍기를 설치하려고 한다. 온풍기의 성능을 테스트하기 위해 구사과는 집을 크기가 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)
- 온풍기가 있는 칸과 바람이 나오는 방향에 있는 칸 사이에는 벽이 없다.
- 온풍기의 바람이 나오는 방향에 있는 칸은 항상 존재한다.
- 같은 벽이 두 번 이상 주어지는 경우는 없다.
예제 입력 1
7 8 1
0 0 0 0 0 0 0 0
0 0 0 0 4 0 0 0
0 0 0 0 0 0 0 0
0 0 5 5 0 0 0 0
0 0 0 0 0 5 0 0
0 0 0 0 0 0 0 0
0 0 0 0 3 0 0 0
3
4 4 1
5 4 0
5 6 0예제 출력 1
1예제 입력 2
7 8 5
0 0 0 0 0 0 0 0
0 0 0 0 4 0 0 0
0 0 0 0 0 0 0 0
0 0 5 5 0 0 0 0
0 0 0 0 0 5 0 0
0 0 0 0 0 0 0 0
0 0 0 0 3 0 0 0
3
4 4 1
5 4 0
5 6 0예제 출력 2
2예제 입력 3
7 8 7
0 0 0 0 0 0 0 0
0 0 0 0 4 0 0 0
0 0 0 0 0 0 0 0
0 0 5 5 0 0 0 0
0 0 0 0 0 5 0 0
0 0 0 0 0 0 0 0
0 0 0 0 3 0 0 0
3
4 4 1
5 4 0
5 6 0예제 출력 3
3예제 입력 4
7 8 70
0 0 0 0 0 0 0 0
0 0 0 0 4 0 0 0
0 0 0 0 0 0 0 0
0 0 5 5 0 0 0 0
0 0 0 0 0 5 0 0
0 0 0 0 0 0 0 0
0 0 0 0 3 0 0 0
3
4 4 1
5 4 0
5 6 0예제 출력 4
53예제 입력 5
7 8 1000
0 0 0 0 0 0 0 0
0 0 0 0 4 0 0 0
0 0 0 0 0 0 0 0
0 0 5 5 0 0 0 0
0 0 0 0 0 5 0 0
0 0 0 0 0 0 0 0
0 0 0 0 3 0 0 0
3
4 4 1
5 4 0
5 6 0예제 출력 5
101예제 입력 6
7 8 100
0 0 0 0 0 0 0 0
5 0 0 0 4 0 0 0
0 0 0 0 0 0 0 0
0 0 5 5 0 0 0 0
0 0 0 0 0 5 0 0
5 0 0 0 0 0 5 0
0 0 0 0 3 0 0 0
0예제 출력 6
93예제 입력 7
7 8 100
0 0 0 0 0 0 5 0
5 4 4 4 4 4 4 0
0 0 0 0 0 0 0 0
0 0 5 5 0 0 0 0
0 0 0 0 0 5 0 0
5 0 0 0 0 0 5 0
0 0 0 0 3 0 0 0
3
4 4 1
5 4 0
5 6 0예제 출력 7
35예제 입력 8
7 8 1000
0 0 0 0 0 0 5 0
5 4 4 4 4 4 4 0
0 0 0 0 0 0 0 0
0 0 5 5 0 0 0 0
0 0 0 0 0 5 0 0
5 0 0 0 0 0 5 0
0 0 0 0 3 0 0 0
3
4 4 1
5 4 0
5 6 0예제 출력 8
101예제 입력 9
7 8 1000
0 0 0 0 0 0 0 0
4 4 4 4 4 4 4 4
0 0 0 0 0 5 0 0
0 0 5 5 0 0 5 0
0 0 0 0 0 5 0 0
5 0 0 0 0 0 5 0
3 3 3 3 3 3 3 3
3
4 4 1
5 4 0
5 6 0예제 출력 9
94
⭕ CODE
from collections import deque
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
# 오른쪽으로
def right(x,y):
global new
q = deque()
visited = [[0] * m for _ in range(n)]
# x,y좌표와 처음 온도 5
q.append((x, y, 5))
while q:
x, y, t = q.popleft()
# 방문한적이 없으면 t만큼 더해준다.
if not visited[x][y]:
new[x][y] += t
# 방문처리
visited[x][y] = 1
# 온도는 1도까지이므로 1보다 작아지면 break
if t < 1:
break
# 오른쪽 위
# 오른쪽 위 좌표가 격자 안에 존재하고
# 오른쪽 위로 가려면 벽이 없어야 하는 조건이
# 자기자신 바로 위가 벽이 아니고 (x, y) not in up_wall
# 자기 위의 오른쪽이 벽이 아니여야한다. (x-1, y) not in right_wall
# 또한 방문한적이 없다면
if 0 <= x - 1 < n and 0 <= y + 1 < m and (x, y) not in up_wall and (x-1, y) not in right_wall and visited[x - 1][y + 1] == 0:
q.append((x - 1, y + 1, t - 1))
# 오른쪽 밑
# 오른쪽 밑 좌표가 격자 안에 존재하고
# 오른쪽 밑으로 가려면 벽이 없어야 하는 조건이
# 자기 밑지점의 위가 벽이 아니고 (x+1, y) not in up_wall
# 자기 밑의 오른쪽이 벽이 아니여야한다. (x+1, y) not in right_wall
# 또한 방문한적이 없다면
if 0 <= x + 1 < n and 0 <= y + 1 < m and (x+1, y) not in up_wall and (x+1, y) not in right_wall and visited[x + 1][y + 1] == 0:
q.append((x + 1, y + 1, t - 1))
# 그냥 오른쪽
# 격자안에 존재
# 자기 바로 오른쪽이 벽이 아니고 방문한 적이 없으면
if 0 <= x < n and 0 <= y+1 < m and (x, y) not in right_wall and visited[x][y+1] == 0:
q.append((x , y+1, t - 1))
# 오른쪽함수와 동일한 방법으로 진행
def left(x,y):
global new
q = deque()
visited = [[0] * m for _ in range(n)]
q.append((x, y, 5))
while q:
x, y, t = q.popleft()
if not visited[x][y]:
new[x][y] += t
visited[x][y] = 1
if t < 1:
break
# 왼쪽 위
if 0 <= x - 1 < n and 0 <= y - 1 < m and (x, y) not in up_wall and (x-1, y-1) not in right_wall and visited[x - 1][y - 1] == 0:
q.append((x - 1, y - 1, t - 1))
# 왼쪽 밑
if 0 <= x + 1 < n and 0 <= y - 1 < m and (x+1, y) not in up_wall and (x+1, y-1) not in right_wall and visited[x + 1][y - 1] == 0:
q.append((x + 1, y - 1, t - 1))
# 그냥 왼쪽
if 0 <= x < n and 0 <= y-1 < m and (x, y-1) not in right_wall and visited[x][y-1] == 0:
q.append((x , y-1, t - 1))
def up(x, y):
global new
q = deque()
visited = [[0] * m for _ in range(n)]
q.append((x, y, 5))
while q:
x, y, t = q.popleft()
if not visited[x][y]:
new[x][y] += t
visited[x][y] = 1
if t < 1:
break
# 오른쪽 위
if 0 <= x - 1 < n and 0 <= y + 1 < m and (x, y) not in right_wall and (x, y + 1) not in up_wall and visited[x - 1][y + 1] == 0:
q.append((x - 1, y + 1, t - 1))
# 왼쪽 위
if 0 <= x - 1 < n and 0 <= y - 1 < m and (x, y - 1) not in right_wall and (x, y - 1) not in up_wall and visited[x - 1][y - 1] == 0:
q.append((x - 1, y - 1, t - 1))
# 그냥 위
if 0 <= x - 1 < n and 0 <= y < m and (x, y) not in up_wall and visited[x - 1][y] == 0:
q.append((x - 1, y, t - 1))
def down(x, y):
global new
q = deque()
visited = [[0] * m for _ in range(n)]
q.append((x, y, 5))
while q:
x, y, t = q.popleft()
if not visited[x][y]:
new[x][y] += t
visited[x][y] = 1
if t < 1:
break
# 오른쪽 아래
if 0 <= x + 1 < n and 0 <= y + 1 < m and (x, y) not in right_wall and (x + 1, y + 1) not in up_wall and visited[x + 1][y + 1] == 0:
q.append((x + 1, y + 1, t - 1))
# 왼쪽 아래
if 0 <= x + 1 < n and 0 <= y - 1 < m and (x, y - 1) not in right_wall and (x + 1, y - 1) not in up_wall and visited[x + 1][y - 1] == 0:
q.append((x + 1, y - 1, t - 1))
# 그냥 아래
if 0 <= x + 1 < n and 0 <= y < m and (x + 1, y) not in up_wall and visited[x + 1][y] == 0:
q.append((x + 1, y, t - 1))
# 온도 조절
def move():
# 2차원 리스트 deepcopy
newarr = [a[:] for a in new]
for i in range(n):
for j in range(m):
# 0이 아닌거에 대해서만 조사하므로
if new[i][j] != 0:
# 4방향에 대해서
for d in range(4):
nx = i + dx[d]
ny = j + dy[d]
# 격자안에 존재하고, 지금 위치가 이동할 위치보다 크다면
if 0 <= nx < n and 0 <= ny < m and new[i][j] > new[nx][ny]:
# 각 방향에 대해서 벽이 존재하지 않는다면
if (d == 0 and (i, j) not in right_wall) or (d == 1 and (i, j - 1) not in right_wall) or (d == 2 and (i, j) not in up_wall) or (d == 3 and (i + 1, j) not in up_wall):
# 이동 지점에는 (두칸의 온도 차이 / 4)를 더해주고
# 원래 자리에는 그만큼 빠져나갔으므로 (두칸의 온도 차이 / 4)를 빼준다
newarr[nx][ny] += (new[i][j] - new[nx][ny]) // 4
newarr[i][j] -= (new[i][j] - new[nx][ny]) // 4
return newarr
# 사이드 체크
def side():
for i in range(n):
for j in range(m):
if i == 0 or i == n-1 or j == 0 or j == m-1:
if new[i][j] >0:
new[i][j] -= 1
# 체크지점 확인
def checkpoint():
for x,y in check:
if new[x][y] < k:
return False
return True
# n*m 배열
# k -> 조사해야하는 온도
n, m, k = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
# 온도를 기록하기 위한 new
new = [[0] * m for _ in range(n)]
# 온풍기 li
li = []
# 나중에 체크해야하는 좌표들
check = []
for i in range(n):
for j in range(m):
if 0 < arr[i][j] < 5:
li.append((i, j, arr[i][j]))
if arr[i][j] == 5:
check.append((i, j))
w = int(input())
right_wall = []
up_wall = []
for _ in range(w):
x, y, t = map(int, input().split())
# t == 0 -> (x,y) 와 (x-1,y) 사이에 벽
# 즉 내 위에 벽
if t == 0:
up_wall.append((x - 1, y - 1))
# t == 1 -> (x,y) 와 (x,y+1) 사이에 벽
# 즉 내 오른쪽 벽
elif t == 1:
right_wall.append((x - 1, y - 1))
# 결과값 result
result = 0
while True:
result += 1
# x,y 좌표와 d 방향
for x,y,d in li:
# d == 1 -> 오른쪽으로
# 온풍기지점 오른쪽부터 온도가 나오므로
# right(x,y+1)을 해준다
if d == 1:
right(x,y+1)
# 온풍기지점 왼쪽부터 온도가 나오므로
# left(x,y-1)을 해준다
elif d == 2:
left(x,y-1)
# 온풍기지점 위쪽부터 온도가 나오므로
# up(x-1,y)을 해준다
if d == 3:
up(x - 1, y)
# 온풍기지점 아래쪽부터 온도가 나오므로
# down(x+1,y)을 해준다
elif d == 4:
down(x + 1, y)
# 온도조절
newarr = move()
# 다시 new를 newarr로 변환
new = newarr
# 사이드 1씩 줄여주는 함수
side()
# 확인하는 좌표가 k보다 큰지 확인
if checkpoint():
break
# 결과값이 100보다 크면 101로 지정하고 그만
if result > 100:
result = 101
break
print(result)✏️ Comment
플레 문제는 처음이다. 그래도 구현이라서 시간은 오래 걸렸지만 풀 수 있었다.
처음에는 온풍기 지점부터 온도가 올라가는 줄 알고 시간을 많이 사용했다. 문제를 꼼꼼히 읽자
그리고 열의 개수는 m개 인데 중간에 함수에서 n개로 범위를 지정하여 계속 index에러가 나오고 다른 정답이 나왔다.
'알고리즘 > 백준' 카테고리의 다른 글
| [BOJ 22945🥇4] 팀 빌딩 (Python) (0) | 2023.10.29 |
|---|---|
| [BOJ 1965🥈2] 상자넣기(Python) (1) | 2023.10.28 |
| [BOJ 20061🥇2] 모노미노도미노 2 (Python) (2) | 2023.10.10 |
| [BOJ 12015 🥇2] 가장 긴 증가하는 부분 수열 2 (Python) (0) | 2023.10.03 |
| [BOJ 2933 🥇1] 미네랄 (Python) (1) | 2023.10.01 |
