문제 링크
https://www.acmicpc.net/problem/2638
🕒 Python 풀이시간: 20분
from collections import deque
dx=[0,0,-1,1]
dy=[-1,1,0,0]
n,m=map(int,input().split())
originBoard=[list(map(int,input().split())) for _ in range(n)]
board=[[0]*(m+2) for _ in range(n+2)]
for i in range(1,n+1):
for j in range(1,m+1):
board[i][j]=originBoard[i-1][j-1]
outAir=set()
def outAirbfs(x,y):
q=deque()
q.append((x,y))
visited=[[False]*(m+2) for _ in range(n+2)]
visited[x][y]=True
outAir=set()
outAir.add((x,y))
while q:
now=q.popleft()
for i in range(4):
nx=now[0]+dx[i]
ny=now[1]+dy[i]
if nx<0 or ny<0 or nx>=n+2 or ny>=m+2:
continue
if visited[nx][ny]:
continue
if board[nx][ny]==1:
continue
outAir.add((nx,ny))
visited[nx][ny]=True
q.append((nx,ny))
return outAir
def cheeseBfs(visited,x,y):
q=deque([(x,y)])
visited[x][y]=True
cheese=set()
cheese.add((x,y))
while q:
now=q.popleft()
for i in range(4):
nx=now[0]+dx[i]
ny=now[1]+dy[i]
if nx<0 or ny<0 or nx>=n+2 or ny>=m+2:
continue
if visited[nx][ny]:
continue
if board[nx][ny]==0:
continue
visited[nx][ny]=True
q.append((nx,ny))
cheese.add((nx,ny))
return cheese
t=0
while True:
outAirSet=outAirbfs(0,0)
if len(outAirSet)==(n+2)*(m+2):
break
visited=[[False]*(m+2) for _ in range(n+2)]
cheese=set()
for i in range(n+2):
for j in range(m+2):
if not visited[i][j] and board[i][j]==1:
cheese|=cheeseBfs(visited,i,j)
for piece in cheese:
x,y=piece
cnt=0
for i in range(4):
nx=x+dx[i]
ny=y+dy[i]
if (nx,ny) in outAirSet:
cnt+=1
if cnt>=2:
board[x][y]=0
t+=1
print(t)치즈 외부 공기 구분 문제! 🧀🌬️
외부의 공기와 맞닿아 있는 치즈와 그렇지 않은 치즈를 구분해야 하는 문제이다. 시뮬레이션과 BFS문제라고 할 수 있다. 데이터의 크기가 100x100으로 커봐야 10,000이므로 탐색에 O(N)이 소요되는 BFS를 여러번 사용해도 상관없으며 시간 문제라 반복량을 고려해보아도 없어지는데 최대 100초 이기 때문에 몇백만 밖에 나오지 않는다.
먼저 외부 공기를 찾는 가장 쉬운 방법은 가장 바깥 부분에 있는 공기 중 하나를 BFS로 탐색하여 이와 이어져 있는 구간을 탐색하는 것인데 이 때, 문제에서 바깥 공기가 아닌 준 NxM 자체에 치즈가 딱 들어맞을 가능성도 있기에 바깥을 한번 공기로 더 감아주어 확실하게 0,0지점을 외부 공기로 만들어준다. 그런다음 0,0을 기준으로 외부 공기를 탐색하면 된다. 외부 공기를 집합에 담아주었다.
그런 후에 치즈를 탐색하고 치즈 중에 외부와 2면 이상 외부와 닿아 있는 치즈를 찾기 위해 BFS로 치즈를 탐색해주고 그 치즈를 하나씩 좌표별로 따져서 저장해두었던 외부공기와 두 개 이상 맞닿아 있다면 치즈를 지운다. 마지막으로 외부 공기의 수가 보드의 크기 만큼 된다면 치즈가 존재하지 않는 것이기 때문에 종료한다.
이렇게 Python으로 백준의 "치즈" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊
