[코딩테스트][백준] 🔥 백준 23289번 "온풍기 안녕!" 문제: Python으로 완벽 해결하기! 🔥

문제 링크

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

🕒 Python 풀이시간: 2시간

from collections import deque

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

r,c,k=map(int,input().split())
blocks=[]
heaters=[]
for i in range(r):
    arr=list(map(int,input().split()))
    for j in range(c):
        if arr[j]==5:
            blocks.append((i,j))
        elif 1<=arr[j]<=4:
            dir=-1
            if arr[j]==1:
                dir=1
            elif arr[j]==2:
                dir=3
            elif arr[j]==3:
                dir=0
            elif arr[j]==4:
                dir=2
            heaters.append((i,j,dir))

w=int(input())
walls=set()
for _ in range(w):
    x,y,t=map(int,input().split())
    walls.add((x-1,y-1,t))

board=[[0]*c for _ in range(r)]
chocolate=0

def isBlocked(x,y,nx,ny,dir):
    if dir==1:
        if x==nx:
            if (x,y,1) in walls:
                return True
        if x-nx==1:
            if (x,y,0) in walls or (x-1,y,1) in walls:
                return True
        if nx-x==1:
            if (x+1,y,0) in walls or (x+1,y,1) in walls:
                return True
    if dir==3:
        if x==nx:
            if (x,y-1,1) in walls:
                return True
        if x-nx==1:
            if (x,y,0) in walls or (x-1,y-1,1) in walls:
                return True
        if nx-x==1:
            if (x+1,y,0) in walls or (x+1,y-1,1) in walls:
                return True
    if dir==0:
        if y==ny:
            if (x,y,0) in walls:
                return True
        if y-ny==1:
            if (x,y-1,1) in walls or (x,y-1,0) in walls:
                return True
        if ny-y==1:
            if (x,y,1) in walls or (x,y+1,0) in walls:
                return True
    if dir==2:
        if y==ny:
            if (x+1,y,0) in walls:
                return True
        if y-ny==1:
            if (x,y-1,1) in walls or (x+1,y-1,0) in walls:
                return True
        if ny-y==1:
            if (x+1,y+1,0) in walls or (x,y,1) in walls:
                return True
    return False

def workHeater(board,heaters):
    for heater in heaters:
        visited=[[False]*c for _ in range(r)]
        x,y,dir=heater
        q=deque()
        q.append((x+dx[dir],y+dy[dir],5))
        visited[x+dx[dir]][y+dy[dir]]=True
        board[x+dx[dir]][y+dy[dir]]+=5
        while q:
            x,y,temp=q.popleft()
            if temp<=0:
                break
            spreadList=[(dir,),(dir,(dir+1)%4),(dir,(dir-1)%4)]
            for k in range(3):
                nx,ny=x,y
                for d in spreadList[k]:
                    nx=nx+dx[d]
                    ny=ny+dy[d]
                if nx<0 or ny<0 or nx>=r or ny>=c:
                    continue
                if visited[nx][ny]:
                    continue
                if isBlocked(x,y,nx,ny,dir):
                    continue
                board[nx][ny]+=temp-1
                visited[nx][ny]=True
                q.append((nx,ny,temp-1))
    return board

def adjustTemp(board,walls):
    temp=[[0]*c for _ in range(r)]
    for i in range(r):
        for j in range(c):
            x,y=i,j
            for k in [1,2]:
                nx=x+dx[k]
                ny=y+dy[k]
                if nx<0 or ny<0 or nx>=r or ny>=c:
                    continue
                if k==1 and (x,y,1) in walls:
                    continue
                if k==2 and (nx,ny,0) in walls:
                    continue
                l=abs(board[nx][ny]-board[x][y])//4
                if board[nx][ny]>board[x][y]:
                    temp[nx][ny]-=l
                    temp[x][y]+=l
                elif board[nx][ny]<board[x][y]:
                    temp[nx][ny]+=l
                    temp[x][y]-=l
    for i in range(r):
        for j in range(c):
            board[i][j]+=temp[i][j]
    return board

def decreaseTemp(board):
    for i in range(r):
        for j in range(c):
            if i==r-1 or j==c-1 or i==0 or j==0:
                if board[i][j]>0:
                    board[i][j]-=1
    return board

def aboveTempK(board,blocks):
    for block in blocks:
        if board[block[0]][block[1]]<k:
            return False
    return True

while True:
    board=workHeater(board,heaters)

    board=adjustTemp(board,walls)

    board=decreaseTemp(board)

    chocolate+=1
    if chocolate>100:
        break

    if aboveTempK(board,blocks):
        break

print(chocolate)

온풍기 안녕! 시뮬레이션 문제! 🌬️❄️

미세먼지 안녕의 다음 편인 온풍기 안녕! 문제이다. 시뮬레이션도 많이 어려워져서 애를 먹었다. 한가지 깨달은 점이 있다면 방향이 복잡하다면 방향을 내맘대로 바꾼다음에 푸는 것이 편하다는 것이다.

먼저 온풍기를 동작시켜준다. 각 온풍기에 대해 단순히 board에는 더하면 되므로 각 히터를 for문으로 불러온다. 이 때, 온풍기의 1~4번 번호에 대해서 입력을 받을 때, 회전을 알기 쉽게 내가 원하는 번호로 바꾸어놓았다. 시작점은 온풍기에서 해당 방향으로 한칸 이동한 점이 시작지점이며 +5를 해준 후, BFS와 마찬가지로 큐에 넣어준다. 이 때, 한번 전파된 곳은 다시 전파될 필요가 없으므로 visited로 방문한 곳을 다시 방문하지 않도록 해준다. 이제 온풍기가 전파되는 방향인 3방향으로 나아가면 되는데 이 때, 현재 방향으로 한칸 나아간 곳, 그 한칸에서 왼쪽으로 꺾은 곳, 오른쪽으로 꺾은 곳 이렇게 3개의 칸으로 나아가는 것을 검사해주면 된다. 영역 내 검사, 방문처리 검사 등을 해주고 중요한 것은 벽으로 막히는지를 검사하여 주어야 한다. 벽으로 막히는지에 대한 검사는 단순히 일일이 작성하는 방법밖에 없는 거 같다. 모든 방향이나 회전에 대해 공통으로 쓰이게 벽을 준것이 아니라 특정 방향과 블록에 고정되어 있는 벽을 준 것이기 때문에 그냥 조건문으로 일일이 막히는지를 표시해 주었다.

이렇게 온풍기의 바람 전파가 끝나면 나머지는 간단하다. 먼저 온도조절을 인접한 모든 관계에 대해서 수행하는데 이때 각 인접한 칸은 다음 칸이 전파할 때 영향을 주므로, 즉 동시에 일어나므로 따로 온도가 높아지고 낮아짐을 기록해 두었다가 나중에 합산한다. 현재 칸을 기준으로 오른쪽과 아랫쪽만 하면 모든 관계가 중복되지 않도록 찾을 수 있으므로 모든 칸에 대해서 이처럼 진행하였다. 벽에 막히는 부분도 이 부분만 신경써서 막히는 부분만 처리해주면 된다. 이후 문제의 조건에 따라 높아지고 낮아짐을 기록해 두었다가 처리해준다.

이제 끝에 있는 테두리의 온도를 1씩 감소시킨다. 그런 후, 전체 과정의 횟수라고 할 수 있는 초콜렛을 증가시킨다. 과정을 끝내는 조건은 초콜릿이 100개가 넘던지 검사하라고 주어진 칸이 모두 k 이상이 되면 탈출한다.

이렇게 Python으로 백준의 "온풍기 안녕!" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊