📌 문제 : 백준 23289번
📌 문제 탐색하기
R : 행의 수 ()
C : 열의 수 ()
K : 검사 온도 ()
W : 벽의 개수 ()
문제 풀이
많이 어려워서 참고하면서 풀었다.
크기가 R×C인 집의 온도를 실시간으로 모니터링하면서 초콜릿을 먹을 때, 총 몇 개를 먹는지 구하는 문제이다.
성능 테스트 작업 순서
- 집에 있는 모든 온풍기에서 바람 1번 나옴
- 온도 조절
- 온도 1 이상인 가장 바깥쪽 칸의 온도 1씩 감소
- 초콜릿 1개 먹기
4-1. 해당 작업 반복
4-2. 먹는 초콜릿의 개수가 100 넘어가면 101 출력 - 모든 칸의 온도가 K 이상인지 검사
5-1. K 이상이면 테스트 중단
5-2. 아니면 1부터 다시 시작
⭐️ 온도 증가 방식
- 온풍기에서 바람 나옴
- 바람 나오는 방향 4가지 중 1개
- 위, 아래, 왼쪽, 오른쪽
- 바람 나오는 방향에 따라 온도 증가
- ⚠️ 바람 1번 나왔을 때 온도 증가
- 바람 나오는 칸 = 항상 온도 5도
- 다른 칸으로 이동
- (x, y)에 바람 도달해 온도
k라면?
- (x-1, y+1), (x, y+1), (x+1, y+1)의 온도 =
k-1- 어떤 칸에 같은 온풍기의 바람 여러 번 도착해도 온도 여러번 상승 ❌
- 벽이 있는 칸은 온풍기 바람 통과 ❌
- 온풍기 여러 개 → 상승한 온도 모두 합한 값이 해당 칸의 상승한 온도
⭐️ 온도 조절 방식
- 모든 인접한 칸에 대해 조절
- 벽이 있으면 온도 조절 ❌
- 모든 칸에 대해 동시에 발생하는 과정
- 온도 높은 칸 → 낮은 칸으로 만큼 조절
- 온도 높은 칸 : 이 값만큼 🔻
- 온도 낮은 칸 : 이 값만큼 🔺
→ 각 과정이 매우 복잡하므로 여러 개의 함수로 나눠서 구현하면 좋을 것 같다.
입력받을 변수들을 정리한다.
- 방 정보 입력
1-1. 온풍기 위치 따로 저장
1-2. 온도 조사 위치 따로 저장 - 벽 정보 입력
이용할 변수들을 정의해준다.
- 벽 정보 저장
1-1.t = 0이면 (x, y)와 (x-1, y) 사이 벽 ⭕️
1-2.t = 1이면 (x, y)와 (x, y+1) 사이 벽 ⭕️ - 초콜릿 개수 저장할 변수
- 온도 조사할 칸 저장할 리스트
- 온풍기 위치 저장할 리스트
온풍기 바람이 1번 나올 때마다 동작해야 하는 일들을 함수로 구현해준다.
- 온도 증가 함수
- 온도 조절 함수
- 온도 1 이상인 가장 바깥쪽 칸 온도 감소 함수
온도 증가 함수
- 행번호, 열번호, 바람 방향 입력
- BFS로 벽 없는 인접 칸 온도 증가
- 방 정보에 접근
- 0 → 빈 칸 = 동작 ❌
- 1 → 바람 오른쪽으로
- 2 → 바람 왼쪽으로
- 3 → 바람 위로
- 4 → 바람 아래로
- 5 → 온도 조사해야 할 칸
- 바람 나오는 칸 = 5도
- 각 칸의 온도는 누적합 계산
- 온풍기 방향에 따라 인접한 부분 접근해 온도 상승
- 그 이후로 0 될 때까지 1 감소
- 벽이 있는지 확인
온도 조절 함수
- 전체 영역에 대해 온도 조절 수행
- 인접 칸과 온도 차이 계산
- 벽 있는지에 따라 조절 가능 여부 판단
- 동시에 온도 조절되는 것에 유의해서 온도 업데이트
바깥쪽 칸 온도 감소 함수
- 바깥쪽 칸 접근
- 온도가 0 이상인 칸 찾아 온도 감소
성능 테스트
- 반복 수행
- 온풍기 작동
- 온도 조절
- 바깥쪽 칸 온도 감소
- 초콜릿 추가
- 온도 조사해야할 위치 접근해 K 이상인지 확인
- 맞다면 테스트 종료
- 아니면 바람 다시 나와서 과정 반복
- 종료 조건
- 모든 칸의 온도가 K 이상
- 초콜릿 개수 100 넘은 경우
가능한 시간복잡도
체스판 입력 →
턴 수 1000번까지 K개의 말 이동하며 함수 수행 →
최종 시간복잡도
로,최악의 경우 이 되어 제한 시간 0.5초 내에 연산이 가능하다.
알고리즘 선택
📌 코드 설계하기
- 온도 증가 함수
- 온도 조절 함수
- 바깥쪽 칸 온도 감소 함수
- R, C, K 입력
- 방 정보 입력
- 벽의 개수 입력
- 벽 정보 입력
- 초콜릿 개수 저장 변수 정의
- 성능 테스트 시작
- 결과 출력
📌 시도 회차 수정 사항
1회차
- 예제 2부터 계속 출력이 101만 나왔다.
- 벽이 있는지 없는지 체크하는 코드를 잘못 구현해 발생한 문제였다.
2회차
- 수정했지만 몇개의 예제에서 출력이 101만 나왔다.
- 온도를 갱신하는 부분에 있어서 동시에 수행해야하는데 그것이 잘못 구현되어 발생한 문제인 것 같다.
📌 정답 코드
import sys
from collections import deque
input = sys.stdin.readline
# 4가지 이동 방향 정의 (0 : 오른쪽, 1 : 왼쪽, 2 : 위, 3 : 아래)
moves = [(0, 1), (0, -1), (-1, 0), (1, 0)]
# 온도 증가 함수
def temp_up(r, c, dir):
visited = [[False] * C for _ in range(R)]
queue = deque([(r + moves[dir][0], c + moves[dir][1], 5)])
while queue:
r, c, temp = queue.popleft()
room[r][c] += temp
if temp > 1: # 온도가 1보다 클 경우, 인접 칸에 온도 전달
nr, nc = r + moves[dir][0], c + moves[dir][1]
if 0 <= nr < R and 0 <= nc < C:
if not wall[dir][r][c] and not visited[nr][nc]:
queue.append((nr, nc, temp - 1))
visited[nr][nc] = True
if dir >= 2: # 위/아래 방향 추가 탐색
if c - 1 >= 0 and not wall[1][r][c] and not wall[dir][r][c - 1] and not visited[nr][c - 1]:
queue.append((nr, c - 1, temp - 1))
visited[nr][c - 1] = True
if c + 1 < C and not wall[0][r][c] and not wall[dir][r][c + 1] and not visited[nr][c + 1]:
queue.append((nr, c + 1, temp - 1))
visited[nr][c + 1] = True
else: # 좌/우 방향 추가 탐색
if r - 1 >= 0 and not wall[2][r][c] and not wall[dir][r - 1][c] and not visited[r - 1][nc]:
queue.append((r - 1, nc, temp - 1))
visited[r - 1][nc] = True
if r + 1 < R and not wall[3][r][c] and not wall[dir][r + 1][c] and not visited[r + 1][nc]:
queue.append((r + 1, nc, temp - 1))
visited[r + 1][nc] = True
# 온도 조절 함수
def control_temp():
new_room = [[room[r][c] for c in range(C)] for r in range(R)]
for r in range(R):
for c in range(C):
for k in [0, 3]: # 오른쪽과 아래 방향
nr, nc = r + moves[k][0], c + moves[k][1]
if 0 <= nr < R and 0 <= nc < C and not wall[k][r][c]:
# 온도 차이 계산
diff = abs(room[r][c] - room[nr][nc]) // 4
# 온도 조절
if room[r][c] > room[nr][nc]:
new_room[r][c] -= diff
new_room[nr][nc] += diff
else:
new_room[r][c] += diff
new_room[nr][nc] -= diff
return new_room
# 바깥쪽 칸 온도 감소 함수
def temp_down():
for i in range(C):
if room[0][i] > 0:
room[0][i] -= 1
if room[R - 1][i] > 0:
room[R - 1][i] -= 1
for i in range(1, R - 1):
if room[i][0] > 0:
room[i][0] -= 1
if room[i][C - 1] > 0:
room[i][C - 1] -= 1
# R, C, K 입력
R, C, K = map(int, input().split())
# 방 정보 입력
room = []
heater = [] # 온풍기 위치
check_temp = [] # 온도 조사 위치
for i in range(R):
row = list(map(int, input().split()))
for j in range(C):
if row[j] == 5:
check_temp.append((i, j)) # 온도 조사할 구간 추가
elif row[j] > 0:
heater.append((i, j, row[j])) # 온풍기 위치 추가
room.append([0] * C) # 온도 저장에 이용
# 벽의 개수 입력
W = int(input())
# 벽 정보 입력
wall = [[[False] * C for _ in range(R)] for _ in range(4)]
for _ in range(W):
x, y, t = map(int, input().split())
x -= 1
y -= 1
if t == 0: # 위/아래 벽
wall[2][x][y] = True
wall[3][x - 1][y] = True
else: # 왼쪽/오른쪽 벽
wall[0][x][y] = True
wall[1][x][y + 1] = True
# 초콜릿 개수 저장 변수 정의
choco = 0
# 성능 테스트 시작
while True:
# 1. 온풍기 작동
for r, c, dir in heater:
temp_up(r, c, dir - 1)
# 2. 온도 조절
room = control_temp()
# 3. 바깥쪽 칸 온도 감소
temp_down()
# 4. 초콜릿 추가
choco += 1
# 5. 온도 조사 위치 확인
all_good = True
for r, c in check_temp:
if room[r][c] < K:
all_good = False
break
# 종료 조건
if all_good or choco > 100:
break
# 결과 출력
print(choco)- 결과
