[백준 23289 / Python] 온풍기 안녕!

온풍기 안녕!

🔍 알고리즘 분류

• 구현
• 시뮬레이션

💡 문제 풀이

1. 벽을 set에 양방향으로 저장하기
2. 바깥쪽 온도 1씩 감소할때 모서리 중복되지 않도록 주의하기

1. 격자 정보 받을 때 행, 열 인덱스 -1씩, 정보칸은 정보 따로 저장 후 0으로 변환

2. 히터 순회하며 온도 상승
   1) queue를 이용해서 한 라인 진행될때마다 상승 온도 1씩 감소시키며 진행
   2) 벽이 있으면 확산 중지

   • 마찬가지로 오, 왼, 위, 아래 각각 케이스 나눠서 확인

   3) 상승 온도가 0이면 확산 멈추기

3. 온도 조절

   • 새로운 2차원 배열에 변화값 저장 후 이후 한꺼번에 적용

4. 바깥쪽 온도 감소시키고 초콜릿 먹기

   • 모서리 중복 주의

5. 조사칸들 순회하며 k이상인지 조사
   1) 모두 만족하면 성능테스트 끝내기
   2) 아니면 계속 진행

6. 정답 출력

📄 코드

• Python

import sys
from collections import deque
input = sys.stdin.readline

r, c, k = map(int, input().split())
arr = []
heaters = set()
inspection = set()

dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]

for i in range(r):
    row = list(map(int, input().split()))
    arr.append(row)
    for j in range(c):
        if row[j] == 5:
            inspection.add((i, j))
            arr[i][j] = 0 # 정보 얻었으면 해당 칸 0으로 교체
        elif row[j] != 5 and row[j] != 0:
            heaters.add((i, j, row[j] - 1))
            arr[i][j] = 0 # 정보 얻었으면 해당 칸 0으로 교체

w = int(input())
walls = set() # 벽 정보
for _ in range(w):
    x, y, t = map(int, input().split())
    x -= 1
    y -= 1
    if t == 0:
        # 양방향으로 저장
        walls.add((x, y, x - 1, y))
        walls.add((x - 1, y, x, y))
    else:
        walls.add((x, y, x, y + 1))
        walls.add((x, y + 1, x, y))

# 해당 칸이 격자판 범위 내인지 검사
def in_range(x, y):
    return 0 <= x < r and 0 <= y < c

# 두 칸 사이에 벽이 있는지 검사
def check_wall(x, y, nx, ny, dir):
    if dir == 0: # 오
        if nx == x: # 바로 오
            return (x, y, x, y + 1) in walls
        elif nx == x - 1: # 위쪽 오
            return (x, y, x - 1, y) in walls or (x - 1, y, x - 1, y + 1) in walls
        elif nx == x + 1: # 아래쪽 오
            return (x, y, x + 1, y) in walls or (x + 1, y, x + 1, y + 1) in walls
    elif dir == 1: # 왼
        if nx == x: # 바로 왼
            return (x, y, x, y - 1) in walls
        elif nx == x - 1: # 위쪽 왼
            return (x, y, x - 1, y) in walls or (x - 1, y, x - 1, y - 1) in walls
        elif nx == x + 1: # 아래쪽 오
            return (x, y, x + 1, y) in walls or (x + 1, y, x + 1, y - 1) in walls
    elif dir == 2: # 위
        if ny == y: # 바로 위
            return (x, y, x - 1, y) in walls
        elif ny == y - 1: # 왼쪽 위
            return (x, y, x, y - 1) in walls or (x, y - 1, x - 1, y - 1) in walls
        elif ny == y + 1: # 오른쪽 위
            return (x, y, x, y + 1) in walls or (x, y + 1, x - 1, y + 1) in walls
    elif dir == 3: # 아래
        if ny == y: # 바로 아래
            return (x, y, x + 1, y) in walls
        elif ny == y - 1: # 왼쪽 아래
            return (x, y, x, y - 1) in walls or (x, y - 1, x + 1, y - 1) in walls
        elif ny == y + 1: # 오른쪽 아래
            return (x, y, x, y + 1) in walls or (x, y + 1, x + 1, y + 1) in walls
    return False

# 온도 상승
def windows(x, y, dir):
    x = x + dx[dir]
    y = y + dy[dir]
    temper = 5
    arr[x][y] += temper
    visited[x][y] = True
    q = deque([(x, y, temper - 1)])
    while q:
        if temper == 0:
            break
        x, y, temper = q.popleft()
        if dir == 0: # 오
            for i in [x - 1, x, x + 1]:
                if in_range(i, y + 1) and not visited[i][y + 1]:
                    if check_wall(x, y, i, y + 1, dir) == False: # 벽 체크
                        arr[i][y + 1] += temper
                        visited[i][y + 1] = True
                        q.append((i, y + 1, temper - 1))
        elif dir == 1: # 왼
            for i in [x - 1, x, x + 1]:
                if in_range(i, y - 1) and not visited[i][y - 1]:
                    if check_wall(x, y, i, y - 1, dir) == False: # 벽 체크
                        arr[i][y - 1] += temper
                        visited[i][y - 1] = True
                        q.append((i, y - 1, temper - 1))
        elif dir == 2: # 위
            for j in [y - 1, y, y + 1]:
                if in_range(x - 1, j) and not visited[x - 1][j]:
                    if check_wall(x, y, x - 1, j, dir) == False: # 벽 체크
                        arr[x - 1][j] += temper
                        visited[x - 1][j] = True
                        q.append((x - 1, j, temper - 1))
        elif dir == 3: # 아래
            for j in [y - 1, y, y + 1]:
                if in_range(x + 1, j) and not visited[x + 1][j]:
                    if check_wall(x, y, x + 1, j, dir) == False: # 벽 체크
                        arr[x + 1][j] += temper
                        visited[x + 1][j] = True
                        q.append((x + 1, j, temper - 1))

# 온도 조절
def control():
    total_temper = [[0] * c for _ in range(r)] # 최종 온도 변화값
    # 총 온도 변화 계산
    for x in range(r):
        for y in range(c):
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if in_range(nx, ny) and arr[x][y] > arr[nx][ny]:
                    if check_wall(x, y, nx, ny, i) == False:
                        diff = (arr[x][y] - arr[nx][ny]) // 4
                        total_temper[x][y] -= diff
                        total_temper[nx][ny] += diff
    # 온도 적용
    for i in range(r):
        for j in range(c):
            arr[i][j] += total_temper[i][j]
            if arr[i][j] < 0:
                arr[i][j] = 0

# 바깥쪽 온도 1씩 감소
def lower_side():
    for i in [0, r - 1]:
        for j in range(c):
            if arr[i][j] - 1 >= 0:
                arr[i][j] -= 1
    # 모서리 중복 처리 안되도록 주의!!
    for j in [0, c - 1]:
        for i in range(1, r - 1):
            if arr[i][j] - 1 >= 0:
                arr[i][j] -= 1

# 조사 칸들 k이상인지 검사
def check_inspection():
    for x, y in inspection:
        if arr[x][y] < k:
            return False
    return True

chocolate = 0

# 성능테스트 하나씩 진행
while True:
    # 1. 히터마다 온도 상승시키기
    for x, y, dir in heaters:
        # 한 히터에 대해서는 중복 방문x
        visited = [[False] * c for _ in range(r)]
        windows(x, y, dir)

    # 2. 온도 조절
    control()
    
    # 3. 바깥쪽 온도 감소
    lower_side()

    # 4. 초콜릿 먹기
    chocolate += 1

    # 5. 조사
    if check_inspection():
        break

    # 100이 넘어가면 멈추기
    if chocolate > 100:
        break

# 정답 출력
print(chocolate)

• 최적화 버전: 바람 확산 칸들 사전에 계산해서 딕셔너리에 저장

import sys
from collections import deque
input = sys.stdin.readline

# 방향: 오른쪽, 왼쪽, 위, 아래
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]

r, c, k = map(int, input().split())
arr = [[0] * c for _ in range(r)]
heaters = []
inspection = set()

for i in range(r):
    row = list(map(int, input().split()))
    for j in range(c):
        if row[j] == 5:
            inspection.add((i, j))
        elif row[j] != 0:
            heaters.append((i, j, row[j] - 1))  # (x, y, dir)

# 벽 정보 입력 및 세트화 (빠른 탐색 가능)
w = int(input())
walls = set()
for _ in range(w):
    x, y, t = map(int, input().split())
    x -= 1
    y -= 1
    if t == 0:  # 위쪽 벽
        walls.add((x, y, x - 1, y))
        walls.add((x - 1, y, x, y))
    else:  # 오른쪽 벽
        walls.add((x, y, x, y + 1))
        walls.add((x, y + 1, x, y))

def in_range(x, y):
    return 0 <= x < r and 0 <= y < c

def wall_blocked(x1, y1, x2, y2):
    return (x1, y1, x2, y2) in walls

# 히터 바람 영향 좌표 캐싱
heater_wind_map = dict()

def precompute_heater_wind():
    for x, y, dir in heaters:
        visited = [[False] * c for _ in range(r)]
        nx, ny = x + dx[dir], y + dy[dir]
        if not in_range(nx, ny):
            continue

        q = deque()
        q.append((nx, ny, 5))
        visited[nx][ny] = True
        temp_list = [(nx, ny, 5)]

        while q:
            cx, cy, val = q.popleft()
            if val == 1:
                continue

            if dir in (0, 1):  # 오 or 왼
                dlist = [(-1, dy[dir]), (0, dy[dir]), (1, dy[dir])]
            else:  # 위 or 아래
                dlist = [(dx[dir], -1), (dx[dir], 0), (dx[dir], 1)]

            for dx_, dy_ in dlist:
                nx, ny = cx + dx_, cy + dy_
                if not in_range(nx, ny) or visited[nx][ny]:
                    continue
                # 벽이 가로막는지 체크
                bx, by = cx, cy
                if wall_blocked(bx, by, bx + dx_, by) or wall_blocked(bx + dx_, by, bx + dx_, by + dy_):
                    continue
                visited[nx][ny] = True
                temp_list.append((nx, ny, val - 1))
                q.append((nx, ny, val - 1))

        heater_wind_map[(x, y, dir)] = temp_list

def apply_wind():
    for key in heater_wind_map:
        for x, y, val in heater_wind_map[key]:
            arr[x][y] += val

def control():
    delta = [[0]*c for _ in range(r)]
    for x in range(r):
        for y in range(c):
            for d in range(4):
                nx, ny = x + dx[d], y + dy[d]
                if not in_range(nx, ny):
                    continue
                if wall_blocked(x, y, nx, ny):
                    continue
                if arr[x][y] > arr[nx][ny]:
                    diff = (arr[x][y] - arr[nx][ny]) // 4
                    delta[x][y] -= diff
                    delta[nx][ny] += diff
    for i in range(r):
        for j in range(c):
            arr[i][j] += delta[i][j]

def lower_side():
    for i in [0, r-1]:
        for j in range(c):
            if arr[i][j] > 0:
                arr[i][j] -= 1
    for j in [0, c-1]:
        for i in range(1, r-1):
            if arr[i][j] > 0:
                arr[i][j] -= 1

def check_inspection():
    for x, y in inspection:
        if arr[x][y] < k:
            return False
    return True

# 사전 계산
precompute_heater_wind()

# 시뮬레이션 시작
choco = 0
while choco <= 100:
    apply_wind()       # 1. 히터 바람 영향 적용
    control()          # 2. 온도 조절
    lower_side()       # 3. 외곽 감소
    choco += 1         # 4. 초콜릿 먹기
    if check_inspection():  # 5. 검사
        break

print(choco)

• 시간복잡도: O(RC)