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

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

23289번: 온풍기 안녕!

이 문제에서 핵심은

어떻게 바람이 퍼지는 걸

구현해낼 것인가입니다.

이 아이디어를 구하기 위해

한참 고민하다가

구글링으로 아이디어를 얻었습니다.

여기서 중요한 부분은

ㄱ벽과

ㄴ벽에 대한 부분입니다.

사실, 벽만 따로 구하면

'이거 별거없는데?'

라고 생각이 들지만

저 벽때문에 상당히 스트레스를 받습니다.

 

먼저 q에 첫 온풍기 발사위치를 넣어줍니다.

그리고 pop을 시킨 다음에

중간 위 아래

각각을 봐줍니다.

뒤벽,ㄱ벽,ㄴ벽이 존재하는 지를 보고

없다면 q에 추가를 시켜주는 방식으로

전개를 할 수 있었습니다.

 

#백준 23289 온풍기 안녕!
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)

저의 처음 방식은

d=1일 때를 기준으로

for문을 돌려

위부터 아래까지 전부 보다가

끝에만 ㄱ벽 ㄴ벽이 있는지만 판단했습니다.

그러다가 구현이 제대로 안 되어 확인해보니

맨 중간꺼빼고는 모두 ㄱ ㄴ 벽을 확인해야했습니다.

이 방식이 어렵기는 했지만

다시 풀어보니 가장 실용적인 느낌이네요.

 

https://chldkato.tistory.com/197

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

제가 참고했던 자료입니다.

보시고 공부하시는 데에 큰 도움이 되시길 바랍니다.

 

(내용추가:2022.10.14)

 

from collections import deque
from copy import deepcopy
dx = [0, 0, 0, -1, 1]
dy = [0, 1, -1, 0, 0]

def inside(x,y):
    if x<0 or x>=R or y<0 or y>=C:
        return False
    return True

def spread():

    for x,y,d in heater:
        nx=x+dx[d]
        ny=y+dy[d]
        room[nx][ny]+=5
        if not inside(nx+dx[d],ny+dy[d]):
            continue
        #방향별로 다르게 퍼트려준다
        #오른쪽 먼저
        q=deque()
        q.append((nx,ny))
        if d==1:
            for f in range(4,0,-1):
                tmp=set()
                flag=False
                for _ in range(len(q)):
                    px,py =q.popleft()

                    #1이라면 더이상 가줄게 없다e
                    if py+1>=C:
                        flag=True
                        break
                    #현재 기준 바로 옆으로 가는지
                    if not 1 in wall[px][py]:
                        tmp.add((px,py+1))

                    #현재기준 대각위로가는지
                    if px-1>=0 and not 0 in wall[px][py] and not 1 in wall[px-1][py]:
                        tmp.add((px-1,py+1))
                    #현재기준 대각선 아래로 가는지
                    if px+1<R and not 0 in wall[px+1][py] and not 1 in wall[px+1][py]:
                        tmp.add((px+1,py+1))
                if flag:
                    break
                if not tmp:
                    break
                for tx,ty in tmp:
                    room[tx][ty]+=f
                    q.append((tx,ty))
        #왼쪽을 향하는 온풍기
        elif d==2:
            for f in range(4, 0, -1):
                tmp = set()
                flag=False
                for _ in range(len(q)):
                    px,py =q.popleft()

                    if py-1<0:
                        flag=True
                        break
                    #현재 기준 바로 옆으로 가는지
                    if not 1 in wall[px][py-1]:
                        tmp.add((px,py-1))

                    #현재기준 대각위로가는지
                    if px-1>=0 and not 0 in wall[px][py] and not 1 in wall[px-1][py-1]:
                        tmp.add((px-1,py-1))
                    #현재기준 대각선 아래로 가는지
                    if px+1<R and not 0 in wall[px+1][py] and not 1 in wall[px+1][py-1]:
                        tmp.add((px+1,py-1))
                if flag:
                    break
                if not tmp:
                    break
                for tx, ty in tmp:
                    room[tx][ty] += f
                    q.append((tx, ty))
        #위인 온풍기
        elif d==3:
            for f in range(4, 0, -1):
                tmp = set()
                flag=False
                for _ in range(len(q)):
                    px,py =q.popleft()

                    if px-1<0:
                        flag=True
                        break
                    #현재 기준 바로 위로 가는지
                    if not 0 in wall[px][py]:
                        tmp.add((px-1,py))

                    #현재기준 대각 왼 로가는지
                    if py-1>=0 and not 0 in wall[px][py-1] and not 1 in wall[px][py-1]:
                        tmp.add((px-1,py-1))
                    #현재기준 대각 우로 가는지
                    if py+1<C and not 0 in wall[px][py+1] and not 1 in wall[px][py]:
                        tmp.add((px-1,py+1))

                if flag:
                    break
                if not tmp:
                    break

                for tx, ty in tmp:
                    room[tx][ty] += f
                    q.append((tx, ty))
        #아래인 온풍기
        elif d==4:
            for f in range(4, 0, -1):
                tmp = set()
                flag=False
                for _ in range(len(q)):
                    px,py=q.popleft()
                    if px+1>=R:
                        flag=True
                        break
                    #현재 기준 바로 아래로 가는지
                    if not 0 in wall[px+1][py]:
                        tmp.add((px+1,py))
                    #현재기준 대각 왼 로가는지
                    if py-1>=0 and not 0 in wall[px+1][py-1] and not 1 in wall[px][py-1]:
                        tmp.add((px+1,py-1))
                    #현재기준 대각 우로 가는지
                    if py+1<C and not 0 in wall[px+1][py+1] and not 1 in wall[px][py]:
                        tmp.add((px+1,py+1))
                if flag:
                    break
                if not tmp:
                    break

                for tx, ty in tmp:
                    room[tx][ty] += f
                    q.append((tx, ty))


def div():
    global room
    temp=deepcopy(room)
    for x in range(R):
        for y in range(C):
            if room[x][y]>0:
                #상하좌우보면서 벽이 있는지 여부 체크
                #상
                if inside(x-1,y) and not 0 in wall[x][y]:
                    if room[x][y]>room[x-1][y]:
                        cha=abs(room[x][y]-room[x-1][y])//4
                        temp[x][y]-=cha
                        temp[x-1][y]+=cha

                #하
                if inside(x+1,y) and not 0 in wall[x+1][y]:
                    if room[x][y]>room[x+1][y]:
                        cha=abs(room[x][y]-room[x+1][y])//4
                        temp[x][y]-=cha
                        temp[x+1][y]+=cha

                #좌
                if inside(x,y-1) and not 1 in wall[x][y-1]:
                    if room[x][y]>room[x][y-1]:
                        cha=abs(room[x][y]-room[x][y-1])//4
                        temp[x][y]-=cha
                        temp[x][y-1]+=cha

                #우
                if inside(x,y+1) and not 1 in wall[x][y]:
                    if room[x][y]>room[x][y+1]:
                        cha=abs(room[x][y]-room[x][y+1])//4
                        temp[x][y]-=cha
                        temp[x][y+1]+=cha

    room=deepcopy(temp)




R,C,K=map(int,input().split())
heater=[]
search=[]

#미리미리, 온도조사칸, 히터칸을 받아준다
for x in range(R):
    pm=list(map(int,input().split()))
    for y in range(C):
        if pm[y]==5:
            search.append((x,y))
        elif 0<pm[y]<5:
            heater.append((x,y,pm[y]))


room=[[0]*C for _ in range(R)]
W=int(input())
wall=[[[]for _ in range(C)] for _ in range(R)]
for _ in range(W):
    x,y,t=map(int,input().split())

    wall[x-1][y-1].append(t)

time=0

while time<=100:
    #1히터조사
    spread()
    # for k in range(R):
    #     print(room[k])
    # print()
    #2퍼지기
    div()
    #3 외곽 감소
    for bx in range(R):
        if bx==0 or bx==R-1:
            for by in range(C):
                if room[bx][by]>0:
                    room[bx][by]-=1

        else:
            for by in [0,C-1]:
                if room[bx][by]>0:
                    room[bx][by]-=1
    # for k in range(R):
    #     print(room[k])
    # print()
    time+=1
    #범위내에 K만큼 들어갔는지 조사하기
    flag=True
    for sx,sy in search:
        if room[sx][sy]<K:
            flag=False
            break
    if flag:
        break


print(time)

집합으로 중복된 걸 받아도 알아서 처리해주도록

코드를 수정해봤습니다.