[백준 2638번] 치즈(파이썬)

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

2638번: 치즈

이 문제는 BFS로 외부 공기를 계속 구해주면서

치즈를 제거하는 문제입니다.

2022.06.30 - [알고리즘 공부] - [백준 2573번] 빙산(파이썬)

[백준 2573번] 빙산(파이썬)

이 문제랑 완전 판박이 수준이죠.

그래서 이 문제를 보고 로직을 짜는 건

그렇게 어렵지 않았습니다.

하지만...

#백준 2638번 치즈
from collections import deque


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

N,M=map(int,input().split())
room=[]
cheese=[]
for i in range(N):
    tmp=list(map(int,input().split()))
    for j in range(M):
        if tmp[j]==1:
            cheese.append([i,j])
    room.append(tmp)

time=0
air=[[0,0]]
while cheese:
    #1 공기 구하기
    visited = [[False] * M for _ in range(N)]
    q=deque()
    for x,y in air:
        q.append([x,y])

    while q:
        px, py = q.popleft()

        for d in range(4):
            nx = px + dx[d]
            ny = py + dy[d]

            if nx < 0 or nx >= N or ny < 0 or ny >= M:
                continue

            if visited[nx][ny] == True:
                continue

            if room[nx][ny] == 1:
                continue
            if [nx,ny] in air:
                continue
            q.append([nx, ny])
            visited[nx][ny] = True
            air.append([nx, ny])


    #2 치즈 날리기
    po=[]
    for x, y in cheese:
        face=0
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]

            if nx < 0 or nx >= N or ny < 0 or ny >= M:
                continue

            if [nx,ny] in air:
            #내가 생각하는 시간초과 포인트
            #air 에 있는 걸 하나하나 다 비교해야하니깐
                face+=1
            if face==2:
                break

        if face>=2:
            po.append([x,y])


    for px,py in po:
        pu=cheese.index([px,py])
        cheese.pop(pu)
        room[px][py]=0
    time+=1
print(time)

 

처음에 제가 작성한 코드.

로직상으로는 괜찮은데...

pypy3로 제출해도 시간초과가 떴습니다.

시간초과가 왜 뜰까를 고민해보니

if [x,y ] in air

이 구문때문이 아닐까 생각했습니다.

air라는 리스트를 구현한 건

외부공기를 bfs하는 시간을 줄이기 위함이었습니다.

하지만 정작 이후에 치즈를 날려버릴때

air의 모든 리스트를 탐색해야하니

이 부분에서 시간초과가 났다고 생각이 들었습니다.

 

#백준 2638번 치즈
from collections import deque


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

N,M=map(int,input().split())
room=[list(map(int,input().split()))for _ in range(N)]

time=0

#다 녹았는지 아닌지 판단하는 함수
#치즈가 하나라도 있으면 True
def melt():
    for x in range(N):
        for y in range(M):
            if room[x][y]==1:
                return True

    return False

while melt():
    #1 치즈 공기 구하기
    visited=[[False]*M for _ in range(N)]
    q=deque()
    q.append([0,0])

    room[0][0]=-1
    while q:
        x,y=q.popleft()
        for d in range(4):
            nx=x+dx[d]
            ny=y+dy[d]
            if nx<0 or nx>=N or ny<0 or ny>=M:
                continue
            if visited[nx][ny]==True:
                continue
            if room[nx][ny]==1:
                continue
            q.append([nx,ny])
            visited[nx][ny]=True
            room[nx][ny]=-1

    #2치즈 날리기
    for x in range(N):
        for y in range(M):
            if room[x][y]==1:
                face=0
                for d in range(4):
                    nx=x+dx[d]
                    ny=y+dy[d]
                    if nx < 0 or nx >= N or ny < 0 or ny >= M:
                        continue

                    if room[nx][ny]==-1:
                        face+=1
                if face>=2:
                    room[x][y]=0


    time+=1
print(time)

 

다르게 수정해서 통과했습니다.

여기서는 특별한 건 없었고

외부공기를 -1로 두어

그냥 빈공간과 외부공기간의 차이를 두었습니다.

외곽에 -1이 2개이상이면 날려버리는 식으로하니

시간초과문제는 뜨지 않았네요.

별도의 배열을 선언하지 않고

주어진 리스트의 값을 조정하여

시간을 세이브하는 방법을 익힐 수 있었습니다.