백준 23289 온풍기 안녕! (파이썬)

https://www.acmicpc.net/problem/23289

23289번: 온풍기 안녕!

1. 문제에서 온풍기 방향 순서에 맞춰서 dx, dy를 만든다. 방향이 1~4이기 때문에 첫 인덱스 값은 비워둔다

2. 온풍기에 대한 리스트 heater와 마지막에 온도를 체크할 리스트 checker를 만든다

   heater에는 해당 좌표와 방향을 저장하고, checker에는 좌표를 저장한다

3. 벽에 대한 정보를 저장할 리스트 wall을 만든다

   해당 좌표에 위, 오른쪽 둘 벽이 있을 경우를 고려해서 0, 1 값을 append 하는 방식으로 구현한다

4. heater에 저장된 값을 불러온다. 다음칸은 항상 칸이 있으므로 다음 칸에 5를 더해준다.

   그 다음칸이 범위 안에 있으면 해당 좌표를 큐에 넣는다

5. 조건에 맞춰서 반복문과 큐를 이용해서 4~1 에 해당하는 값을 더해준다

   방향 d에 맞춰서 바람을 이동가능한 만큼 이동하면서 값을 갱신한다.

   각 방향에 맞게 벽을 체크하면서 잘 이동하면 된다.

6. 각 방향에서 다음칸으로 더이상 이동할 수 없으면 flag 변수를 1로 하고 break한다

   flag가 1이거나 큐가 비어있으면 문제에서의 1번 과정이 끝났으므로 2번 과정으로 넘어간다

7. 2번 과정에서 온도 조절은 동시에 진행되므로 temp_a에 현재 값들을 복사한다

   [0, 0] 좌표부터 순서대로 오른쪽 좌표값, 아래 좌표값을 비교하면서 전체 칸의 온도를 조절한다

8. 3번 과정은 테두리 칸의 온도를 빼주면 된다.

9. 최종 출력이 될 cnt에 1을 더해주고 checker의 좌표를 불러와서 모든 칸의 온도가 k를 넘는지 확인한다.

import sys
from copy import deepcopy
from collections import deque

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


def func(x, y, f):
    if check[x][y] == 0:
        check[x][y] = 1
        a[x][y] += f
        q.append([x, y])


r, c, k = map(int, input().split())
heater, checker = [], []
for i in range(r):
    a = list(map(int, input().split()))
    for j in range(c):
        if 0 < a[j] < 5:
            heater.append([i, j, a[j]])
        elif a[j] == 5:
            checker.append([i, j])

w = int(input())
wall = [[[] for _ in range(c)] for _ in range(r)]
for _ in range(w):
    x, y, d = map(int, input().split())
    wall[x-1][y-1].append(d)

a = [[0] * c for _ in range(r)]
cnt = 0
while True:
    for i, j, d in heater:
        q = deque()
        check = [[0] * c for _ in range(r)]
        nx, ny = i + dx[d], j + dy[d]
        a[nx][ny] += 5

        if not 0 <= nx + dx[d] < r or not 0 <= ny + dy[d] < c:
            continue

        q.append([nx, ny])
        flag = 0
        for f in range(4, 0, -1):
            for _ in range(len(q)):
                x, y = q.popleft()

                if d == 1:
                    if y + 1 >= c:
                        flag = 1
                        break
                    if 1 not in wall[x][y]:
                        nx, ny = x, y + 1
                        func(nx, ny, f)
                    if x - 1 >= 0:
                        if 0 not in wall[x][y] and 1 not in wall[x - 1][y]:
                            nx, ny = x - 1, y + 1
                            func(nx, ny, f)
                    if x + 1 < r:
                        if not wall[x + 1][y]:
                            nx, ny = x + 1, y + 1
                            func(nx, ny, f)

                elif d == 2:
                    if y - 1 < 0:
                        flag = 1
                        break
                    if 1 not in wall[x][y - 1]:
                        nx, ny = x, y - 1
                        func(nx, ny, f)
                    if x - 1 >= 0:
                        if 1 not in wall[x - 1][y - 1] and 0 not in wall[x][y]:
                            nx, ny = x - 1, y - 1
                            func(nx, ny, f)
                    if x + 1 < r:
                        if 1 not in wall[x + 1][y - 1] and 0 not in wall[x + 1][y]:
                            nx, ny = x + 1, y - 1
                            func(nx, ny, f)

                elif d == 3:
                    if x - 1 < 0:
                        flag = 1
                        break
                    if 0 not in wall[x][y]:
                        nx, ny = x - 1, y
                        func(nx, ny, f)
                    if y - 1 >= 0:
                        if not wall[x][y - 1]:
                            nx, ny = x - 1, y - 1
                            func(nx, ny, f)
                    if y + 1 < c:
                        if 0 not in wall[x][y + 1] and 1 not in wall[x][y]:
                            nx, ny = x - 1, y + 1
                            func(nx, ny, f)

                else:
                    if x + 1 >= r:
                        flag = 1
                        break
                    if 0 not in wall[x + 1][y]:
                        nx, ny = x + 1, y
                        func(nx, ny, f)
                    if y - 1 >= 0:
                        if 0 not in wall[x + 1][y - 1] and 1 not in wall[x][y - 1]:
                            nx, ny = x + 1, y - 1
                            func(nx, ny, f)
                    if y + 1 < c:
                        if 1 not in wall[x][y] and 0 not in wall[x + 1][y + 1]:
                            nx, ny = x + 1, y + 1
                            func(nx, ny, f)

            if flag == 1 or len(q) == 0:
                break

    temp_a = deepcopy(a)
    for x in range(r):
        for y in range(c):
            dir = []
            if x < r - 1 and 0 not in wall[x + 1][y]:
                dir.append(4)
            if 1 not in wall[x][y]:
                dir.append(1)

            for d in dir:
                nx, ny = x + dx[d], y + dy[d]
                if 0 <= nx < r and 0 <= ny < c:
                    if a[x][y] > a[nx][ny]:
                        diff = (a[x][y] - a[nx][ny]) // 4
                        temp_a[x][y] -= diff
                        temp_a[nx][ny] += diff
                    elif a[x][y] < a[nx][ny]:
                        diff = (a[nx][ny] - a[x][y]) // 4
                        temp_a[x][y] += diff
                        temp_a[nx][ny] -= diff
    a = temp_a

    for i in range(r):
        if i == 0 or i == r - 1:
            for j in range(c):
                if a[i][j] > 0:
                    a[i][j] -= 1
        else:
            for j in [0, c - 1]:
                if a[i][j] > 0:
                    a[i][j] -= 1

    cnt += 1
    if cnt > 100:
        break

    flag = 0
    for x, y in checker:
        if a[x][y] < k:
            flag = 1
            break
    if flag == 0:
        break

print(cnt)