[BOJ/백준] 23289 온풍기 안녕! 파이썬

문제 링크 : https://www.acmicpc.net/problem/23289

23289번: 온풍기 안녕!

 

구현문제이다.

온풍기에 의한 온도 조절은 바로 적용해도 되지만 온도차에 의한 온도 조절은 한번에 진행되야한다.

 

그래서 나는 2차원 배열에 3개의 원소를 넣었다.

현재 온도, 현재 지점에 들어온 온도, 현재 지점에서 나간온도

들어온 온도는 주변 다른 칸에 의해 현재 칸이 높여진 값을 누적한다.

나간 온도는 주변 칸의 온도를 높였을 때 그 높인 값을 누적한다.

 

그리고 주의해야할 점이라면 벽이다.

벽이 0이라면 현재 칸에서는 위쪽으로, 위쪽 칸에서는 아래쪽으로 벽이 생긴것이다.

 

그래서 나는 벽을 체크할때 현재 칸이 아닌 다음칸의 벽에서 현재칸을 바라보는 것을 체크했다.

이유는 딱히 없다. 그게 편했다.

 

이제 문제 그대로 구현하면 된다.

 

온풍기에 의한 온도 조절은 첫칸은 바로 5로 세팅하고 다음부터 반복문으로 구현했다.

첫칸을 큐에 넣고 시작한다.

 

우선 방향을 위 : 0, 오른쪽 : 1, 아래 : 2, 왼쪽 : 3으로 dx,dy를 설정했다.

오른쪽 방향 기준으로 오른쪽 위칸, 오른쪽칸, 오른쪽 아래칸 순으로 탐색했다.

즉 전방향, 현재 방향, 다음방향 으로 탐색하면 된다.

 

이때 대각선 칸은 벽이 중요하다.

오른쪽 위칸이라고 한다면 바람이 「 모양으로 퍼진다 생각하면 된다.

오른쪽 아래칸이라고 한다면 바람이 ㄴ 모양으로 퍼진다 생각하면 된다.

그래서 그 방향의 벽이 없어야하므로 체크해주자.

 

경로에 벽이 없다면 온도를 높혀주고 방문체크를하고 큐에 넣자.

이때 큐가 비거나 amount가 0이 될때까지 수행하자.

amount는 5에서 시작해서 하나씩 줄기 때문이다.

 

큐가 비었다는건 다음이 다 벽이거나 범위 밖의 칸인거다.

 

 

다음 온도차에 의한 온도조절을 하자.

현재 칸에서 4방향을 보면서 온도를 체크하자. 벽이 없고 현재 칸보다 온도가 낮다면

다음 칸 1번째 값에 온도차를 더해주자.

그리고 현재칸 2번째 값에 온도차를 더해주자.

앞에서 말했듯이 0번째는 현재 온도, 1번째는 현재 지점에 들어온 온도, 2번째는 현재 지점에서 나간 온도이다.

 

다음 다시 모든칸을 돌면서 온도를 조절하자.

현재 온도 += 현재 지점에 들어온 온도 - 현재 지점에서 나간 온도

로 계산 될 것이다.

 

마지막으로 테두리칸의 온도가 1이상이라면 -1 해주자.

 

이제 이 목표 칸이 모두 k이상이 될때 까지 수행하자.

중간에 초콜릿이 100이라면 101을 출력하고 종료하자.

 

from sys import stdin
from collections import deque

input = stdin.readline
dx = [-1,0,1,0]
dy = [0,1,0,-1]

r,c,k = map(int, input().split())
temperature = [[[0,0,0] for _ in range(c)] for _ in range(r)]
visited = [[0]*c for _ in range(r)]
visited_num = 0

targets = []
heaters = []
for x in range(r):
    tmp = list(map(int, input().split()))
    for y in range(c):
        if tmp[y] == 5:
            targets.append((x,y))
        elif tmp[y] > 0:
            if tmp[y] == 1:
                typ = 1
            elif tmp[y] == 2:
                typ = 3
            elif tmp[y] == 3:
                typ = 0
            else:
                typ = 2
            heaters.append((x,y,typ))

w = int(input())
wall_board = [[[False]*4 for _ in range(c)] for _ in range(r)]
for _ in range(w):
    x,y,t = map(int, input().split())
    x -= 1
    y -= 1
    if t == 0:
        wall_board[x][y][0] = wall_board[x-1][y][2] = True
    else:
        wall_board[x][y][1] = wall_board[x][y+1][3] = True

def solv():
    answer = 0
    while True:
        spread_heat()
        set_temperature()
        answer += 1
        if check_targets():
            print(answer)
            return
        if answer == 100:
            print(101)
            return

def check_targets():
    for x,y in targets:
        if temperature[x][y][0] < k:
            return False
    return True
def set_temperature():
    global temperature

    for x in range(r):
        for y in range(c):
            if temperature[x][y][0] == 0:
                continue
            for d in range(4):
                nx = x + dx[d]
                ny = y + dy[d]
                if point_validator(nx,ny,(d+2)%4,False) and temperature[x][y][0] > temperature[nx][ny][0]:
                    temperature[nx][ny][1] += (temperature[x][y][0]-temperature[nx][ny][0])//4
                    temperature[x][y][2] += (temperature[x][y][0]-temperature[nx][ny][0])//4

    for x in range(r):
        for y in range(c):
            temperature[x][y][0] += temperature[x][y][1]-temperature[x][y][2]
            temperature[x][y][1] = temperature[x][y][2] = 0

    for x in range(r):
        for y in range(c):
            if x == 0 or y == 0 or x == r-1 or y == c-1:
                if temperature[x][y][0] > 0:
                    temperature[x][y][0] -= 1
def spread_heat():
    global temperature,visited,visited_num

    for sx,sy,typ in heaters:
        visited_num += 1
        sx += dx[typ]
        sy += dy[typ]

        q = deque([(sx,sy)])
        visited[sx][sy] = visited_num

        temperature[sx][sy][0] += 5

        for amount in range(4,0,-1):
            if not q:
                break
            q_len = len(q)
            for idx in range(q_len):
                x,y = q.pop()
                nx = x + dx[typ] + dx[(typ-1)%4]
                ny = y + dy[typ] + dy[(typ-1)%4]
                if point_validator(nx,ny,(typ+2)%4) and not wall_board[x][y][(typ-1)%4]:
                    temperature[nx][ny][0] += amount
                    visited[nx][ny] = visited_num
                    q.appendleft((nx,ny))

                nx = x + dx[typ]
                ny = y + dy[typ]
                if point_validator(nx,ny,(typ+2)%4):
                    temperature[nx][ny][0] += amount
                    visited[nx][ny] = visited_num
                    q.appendleft((nx, ny))

                nx = x + dx[typ] + dx[(typ+1)%4]
                ny = y + dy[typ] + dy[(typ+1)%4]
                if point_validator(nx,ny,(typ+2)%4) and not wall_board[x][y][(typ+1)%4]:
                    temperature[nx][ny][0] += amount
                    visited[nx][ny] = visited_num
                    q.appendleft((nx,ny))

def point_validator(x,y,typ,flag=True):
    if x < 0 or y < 0 or x >= r or y >= c:
        return False
    elif wall_board[x][y][typ]:
        return False
    elif flag and visited[x][y] == visited_num:
        return False
    return True

solv()