[Python] DFS/BFS - 2636. 치즈(골4) / 경계면 탐색

목차

1. 문제

2. 핵심 아이디어

3. 코드

4. 배운 점

---

 

1. 문제

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

2636번: 치즈

---

2. 핵심 아이디어

2-1) 경계면 탐색

지금껏 1로 구성되어 있는 영역을 탐색해왔다면 이번에는 0과 맞닿은 1을 탐색해야 하는 문제였다.

즉, 가장자리인 (0,0)부터 공기층을 탐색하다가 치즈층(1)을 만나면 그 좌표층을 melt리스트에 추가한다.

 

이후, 녹여야하는 melt층의 좌표를 하나씩 꺼내며 치즈를 0으로 녹여준다.

 

2-2) 치즈가 없어질때까지 텀 반복

 

>> 한 텀에서 해야할 일

- bfs를 통해 경계면 치즈 녹이기

- 녹인 치즈의 양만큼 전체 치즈에서 빼주기

- 치즈 양이 0이 되면 break

 

2-3) 매 텀마다 방문값 초기화

치즈가 모두 없어질 때까지 탐색을 여러번 방문해야 하기때문에

visited 2차원 배열을 매 텀마다 초기화 해주어야 한다.

 

만약 초기화를 안한다면 방문했었던 2차원 좌표가 그대로 유지되어

경계면 치즈를 탐색하지 못한다.

---

3. 코드

#2636 치즈 -> bfs

from collections import deque

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

# 가장자리부터 공기와 맞닿은 'c'부분 녹이는 bfs
def bfs():
  #0,0에서부터 탐색 시작
  q= deque([(0,0)])  
  visited[0][0]=1
  
  #녹는 부분을 담는 리스트
  melt=[]

  while(q):
    x,y= q.popleft()

    for i in range(4):
      nx= x+dx[i]
      ny= y+dy[i]
		
      # 범위는 오버하지 않는가?
      if nx<0 or ny<0 or nx>=n or ny>=m:
        continue
		
      # 만약 공기층이라면 -> 탐색 계속하기
      if graph[nx][ny]==0 and visited[nx][ny]==0:
        visited[nx][ny]=1
        q.append((nx, ny))
      
      # 만약 공기에 맞닿은 치즈 층이라면 -> melt리스트에 넣기
      if graph[nx][ny]==1 and visited[nx][ny]==0: 
        visited[nx][ny]=1
        melt.append((nx, ny))

  # 맞닿은 치즈를 녹여주자
  for x,y in melt:
    graph[x][y]=0
  
  # 녹는 치즈의 양 반환
  return len(melt)

#graph 입력값 초기화
n,m= map(int, input().split())

cheese=0
graph=[]
for i in range(n):
  graph.append(list(map(int, input().split())))
  cheese +=(sum(graph[i])) # 전체 치즈의 양

cnt=0

while(1):
  
  #방문 값 초기화가 필요(중요)
  visited=[[0]*m for _ in range(n)] 
  
  cnt+=1
  k=bfs() #치즈를 녹이기
  cheese-=k

  if cheese==0:
    print(cnt) # 텀의 개수
    print(k) #마지막에 녹인 치즈의 양
    break

---

4.배운 점

경계면 탐색을 처음 해보았다.

bfs가 1로 구성되어 있는 영역구하기뿐만 아니라

적절한 조건 설정을 통해 0과 1의 경계면 탐색을 할 수 있다는 사실을 알게되었다.

 

어느정도 탐색에 자신감이 생겼었는데

아직 갈길이 멀어보인다..