반응형
딱봐도 BFS 냄새가 진하게 나는 문제.
차이점은 외부공기와 내부공기의 구별이다.
힌트는 모눈종이 바깥쪽에는 치즈가 없다는 점이다.
코드 구성
0. (0,0)에서 bfs를 진행시켜 진행된 좌표를 vis에 표기한다.
1. vis와 기존 좌표배열(l)의 합이 0이라면, 내부공기에 해당하므로, 2로 변환해준다.
2. 치즈를 찾는다.
3. 치즈 좌표 중 위아래오른쪽왼쪽을 비교하여 1개 이상의 방향에서 외부공기(0)가 찾아지면 제거한다.
4. 내부공기에 해당하는 좌표를 0으로 바꾸어 준다.
5. 이하 t번 반복하여 합이 0이될때까지 계속한다.
코드
from collections import deque
import sys
sys.setrecursionlimit(10**5)
input=sys.stdin.readline
#(0,0)에서 부터 bfs실행, 기존l과 합을 구해서 0인 부분을 내부공기(2)로 갱신
def insidebfs():
oxy=[]
q=deque()
q.append((0,0))
vis=[[0 for x in range(m)] for y in range(n)]
while q:
x,y=q.popleft()
a=[-1,1,0,0]
b=[0,0,-1,1]
for t in range(4):
X=x+a[t]
Y=y+b[t]
if 0<=X<n and 0<=Y<m and l[X][Y]==0 and vis[X][Y]==0:
q.append((X,Y))
vis[X][Y]=1
insideoxy=[]
for x in range(n):
for y in range(m):
tmp=l[x][y]+vis[x][y]
if tmp==0:
insideoxy.append([x,y])
for t in insideoxy:
l[t[0]][t[1]]=2
#내,외부 공기를 구분한 뒤에 2개 이상 닿은 치즈를 제거한 후에, 내부공기를 다시 확인
def cheese():
cheese=[]
insidebfs()
for x in range(n):
for y in range(m):
if l[x][y]==1:
cheese.append([x,y])
a=[-1,1,0,0]
b=[0,0,-1,1]
release=[]
for t in cheese:
x=t[0]
y=t[1]
cnt = 0
for i in range(4):
X=x+a[i]
Y=y+b[i]
if 0<=X<n and 0<=Y<m and l[X][Y]==0:
cnt+=1
if cnt>1:
release.append([x,y])
for x in release:
l[x[0]][x[1]]=0
for x in range(n):
for y in range(m):
if l[x][y]==2:
l[x][y]=0
#반복및출력
def check(t):
SUM=0
for x in range(n):
SUM+=sum(l[x])
if SUM==0:
print(t)
return
else:
cheese()
check(t+1)
n,m=map(int,input().split())
l=[]
for _ in range(n):
l.append(list(map(int,input().split())))
check(0)반응형
