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

import sys
from collections import defaultdict,deque
def input():
    return sys.stdin.readline()
def outOfBound(x,y):
    if 0<=x<N and 0<=y<M:
        return False
    return True
def check(position):
    for x,y in position:
        if arr[x][y] <K:
            return True
    return False
def blocking(a,b):
    if block_air[a].get(b):
        return True
    return False
def air_dire(dir):
    swap_dir = [[],[3,4],[3,4],[1,2],[1,2]]
    return [[dir],[swap_dir[dir][0],dir],[swap_dir[dir][1],dir]]
def calcurate(conditioner):
    air = [[0 for _ in range(M)] for _ in range(N)]
    for x,y in conditioner:
        dir = conditioner[(x,y)]
        x = x + dx[dir]
        y = y + dy[dir]
        air[x][y] += 5
        visited = set()
        visited.add((x,y))
        queue = deque()
        queue.append((x,y,5))

        while queue:
            x,y,cnt = queue.popleft()

            for total_dir in air_dire(dir):
                cx,cy = x,y
                for i in total_dir:
                    nx = cx + dx[i]
                    ny = cy + dy[i]
                    if outOfBound(nx,ny):break
                    if blocking((cx,cy),(nx,ny)):break
                    cx,cy = nx,ny
                else:
                    if (cx,cy) not in visited:
                        visited.add((cx,cy))
                        air[cx][cy] = air[cx][cy] + cnt -1
                        if cnt >2:
                            queue.append((cx,cy,cnt-1))
    return air
def blow():
    temp = [[0 for _ in range(M)] for _ in range(N)]
    for x in range(N):
        for y in range(M):

            for i in range(1,5):
                nx = x + dx[i]
                ny = y + dy[i]
                if outOfBound(nx,ny):continue
                if blocking((x,y),(nx,ny)):continue
                if arr[x][y] >= arr[nx][ny] + 4:
                    gap = (arr[x][y] - arr[nx][ny])//4
                    temp[x][y] -= gap
                    temp[nx][ny] += gap

    for x in range(N):
        for y in range(M):
            arr[x][y] += temp[x][y]
            if arr[x][y]<0:
                arr[x][y] = 0
def down():
    for x in range(N):
        for y in range(M):
            if x == 0 or y == 0 or y == M-1 or x == N-1:
                if arr[x][y]:
                    arr[x][y] -= 1
N,M,K = map(int,input().split())

arr = [[0 for _ in range(M)] for _ in range(N)]
dx = [0,0,0,-1,1]
dy = [0,1,-1,0,0]
air_conditioner = {}
check_position = []
for x in range(N):
    temp = list(map(int,input().split()))
    for y in range(M):
        if temp[y] and temp[y]<5:
            air_conditioner[(x,y)] = temp[y]
        elif temp[y] == 5:
            check_position.append((x,y))

W = int(input())
block_air = defaultdict(dict)
for _ in range(W):
    x,y,c = map(int,input().split())
    x -= 1
    y -= 1
    if c == 0:
        block_air[(x,y)][(x-1,y)] = 1
        block_air[(x-1,y)][(x,y)] = 1
    else:
        block_air[(x,y)][(x,y+1)] = 1
        block_air[(x,y+1)][(x,y)] = 1
temperature_arr = calcurate(air_conditioner)

time = 0
while check(check_position) and time<=100:
    
    for x in range(N):
        for y in range(M):
            arr[x][y] += temperature_arr[x][y]
    blow()
    down()
    time += 1
print(time)

하반기 삼성 기출 문제라서 한번 풀어봤다.

 

삼성 기존 문제들이 그랬던 것처럼 시키는 대로 시뮬레이션을 돌면 되는 문제였다.

 

문제를 읽어보면 1턴에 차례대로 일정한 순서대로 한다.

 

1. 집에 있는 모든 온풍기에서 바람이 한번 나옴

2. 온도가 조절됨

3. 바깥의 온도가 1씩 감소

4. 1턴이 증가하고, 조사하는 모든 칸이 K도 이상이면 종료, 아니면 다시 처음부터 시작

 

총 4단계로 나뉘어져있고, 이걸 무한히 반복하면 된다.

 

그러면 이 문제를 풀기 위한 사전조건들을 먼저 구해주고, 각 단계별로 함수로 나누어서, 진행을 하면 된다.

 

그리고 이 문제를 풀면서 어려운 변수가 되는 것은 벽을 어떻게 판별을 헐것이냐 이다.

 

이 문제는 2차원 dict를 통해 해결를 했다. 문제에서 벽은 총 2종류로 가로로 세워진 벽, 세로로 세워진 벽이다.

 

그러면 이 벽을 어떻게 판별을 할것인가가 고민이었다. 이 문제는 a라는 위치에서 b라는 위치를 갈때 벽이 있느냐를 판별하면 되므로 2차원 dict를 통해 문제를 해결했다.

c가 0이라면, (x,y) 와 (x-1,y)를 키를 하는 dict를 만들어두고, 우리가 이동을 할때 해당 키가 존재하는지 유무를 통해, 벽이 존재하는지 안하는지를 판별할 수 있게 된다.

c가 1일때에도 동일하게 (x,y)와 (x,y+1)를 키로 하는 dict를 만들어주면 된다.

 

이렇게 먼저 사전작업을 해준뒤 위의 단계를 진행해주면 된다.

 

1번 로직인 집에 있는 모든 온풍기에서 바람이 1번 나옴은, 문제에서 주어진 것처럼 매턴 마다 일정한 값이, 일정한 칸에 더해지는 걸 알 수 있다.

 

그러므로, 먼저 clacurate 라는 함수를 통해, 모든 온풍기들이 바람이 불었을 때, 늘어나는 온도들을 미리 구해놓았다.

 

이렇게 1번 구해놓으면 N*M 을 반복하면서 원래 arr에 더해주면 끝이기 때문이다.

 

온풍기가 퍼지는 방향을 보면, 온풍기가, 동,서 방향으로 있다면, 동 서 방향으로 한칸씩 전진을 하며,

 

대각선 방향으로 진행될 때에는 먼저, 북이나 남 방향으로 퍼진뒤 동서 방향으로 진행을 하게 된다.

 

이 점을 이용하여, air_dire라는 함수를 통해, 온풍기가 진행하는 방향들을 먼저 구해주면 된다. 총 3가지 방향으로,

 

온풍기의 방향대로 나아가는 것과, 온풍기가 바라보는 방향의 90도 방향으로 먼저 꺾은뒤

 

온풍기가 바라보는 방향으로 진행을 하는 총 3가지의 방향을 한다.

 

위와 같이 준비를 한뒤에 bfs를 돌려주면 된다. 이 바람이 범위를 벗어나는지, 벽에 가로막혔는지를 판별을 하고, 

 

cnt가 2까지만 돌려주면 된다.

 

여기서 python의 for else 문을 사용할줄 알면 쉽게 트리거를 구분할 수 있다.

 

 

이렇게 우리는 calcurate를 통해, 우리는 온풍기가 켜졌을 때, 온도의 변화를 미리 구할 수 있게 되었다.

 

 

2번 로직은 인제 온도차를 통해, 온도가 조절되는 것을 구현을 해야한다. 이 부분도 비슷하게, N*M의 각 지점마다,

 

상하좌우를 탐색한 뒤, 벽으로 막혀있는지, 범위를 벗어나는지 먼저 판별을 하고 난뒤에,

 

인접한 위치의 온도가 현재 위치보다 온도가 낮으면, 그 온도의 gap을 4로 나눈 몫을 temp에 각각 마킹을 해준다.

 

온도가 높았던 곳은 - 온도가 낮았던 곳은 +를 해준다.

 

이렇게 모든 작업을 마친 뒤, 원본 배열에 더해주는 작업을 하고, 혹시 모르니, 음수는 0으로 바꿔주는 로직을 넣어줬다.

 

 

우리는 이렇게 크게 1,2번 로직을 완성했고, 인제 3,4번 로직을 구해놓으면 된다.

 

다음으로 3번 로직은 제일 외부의 온도가 1도씩 줄어든다고 했는데 사실 이건 구하기 쉬운 문제이다.

 

N*M 만큼 모든 점을 돌아다니면서 x가 0이거나 x가 N-1이거나 y가 0이거나 M-1일때에가 제일 외부인 걸 알 수 있다.

 

그리고 해당 위치의 온도가 1도이상 일때 온도를 1도씩 줄여주면 된다.

 

 

마지막으로 4번은 조사하는 부분들을 처음 입력이 들어왔을때, 따로 빼놓고,

 

이걸 반복문을 돌면서 한 곳의 온도가 K 미만이면, True 모든 곳의 온도가 K이상이면 False를 반환하는 check 함수를 만들어두었다.

 

그리고 모든 턴의 횟수가 101이 넘어가면 101로 출력해야하므로, time이 100이하일떄까지만 돌아가도록 while문을 작성해놓았다.

 

이 문제에서 크게 고민해야했던 부분은 3가지이다.

 

첫번째로, 1번 로직은 매번 반복되는 것이므로, 한번만 구해놓으면, 그 온도 변화량을 다시 구할 필요없이, 이용을 하면 된다.

 

두번째는 벽을 어떻게 구현을 할것인지 하는 것이다. 나는 이 문제를 풀때 두 튜플의 key값으로 하는 dict를 통해 만들어 뒀는데, 다른 방법들도 있을 것이다. 이 벽을 판별하는 것이 이 문제의 중요 포인트 중 하나였다.

 

그리고 마지막으로, 온풍기의 대각선 이동을 어떻게 구현을 하는것이냐였다.

 

온풍기의 진행방향에 벽이 세워져 있다하더라도, 온풍기의 90도 되는 방향에 벽이 없으면,

 

그 벽을 통해, 다음 칸으로 진행을 할수도 있었다. 그렇기 때문에, 온풍기의 대각선 이동방향을 어떻게 구현 할것인지가

 

꽤나 고민을 해야했던 부분이였다.

 

이 문제는 각각의 로직 별로, 함수를 만들어놓고, 그 함수 내에서 한가지 기능을 완료하는 식으로 해야,

 

어떤 부분에 에러가 발생했을때, 금방 알아차릴 수 있는 문제였다.