문제

N x M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어있는 경우 서로 연결되어있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 떄 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오. 다음의 4 x 5 얼음틀 예시에서는 아이스크림이 총 3개 생성된다.

입력

• 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다. (1 <= N, M <= 1,000)
• 두 번째 줄부터 N + 1 번째 줄까지 얼음 틀의 형태가 주어진다.
• 이때 구멍이 뚫려있는 부분은 0, 그렇지 않은 부분은 1이다.

출력

한 번에 만들 수 있는 아이스크림의 개수를 출력한다.

예제 입출력

• 예제 1

# 입력
4 5
00110
00011
11111
00000

# 출력
3

• 예제2

# 입력
15 14
00000111100000
11111101111110
11011101101110
11011101100000
11011111111111
11011111111100
11000000011111
01111111111111
00000000011111
01111111111000
00011111111000
00000001111000
11111111110011
11100011111111
11100011111111

# 출력
8

BFS

먼저, 방문여부를 기록할 2차원 행렬을 만들었다. 그리고, 각 0으로 이루어진 영역들에 대한 탐색을 진행하며 두가지 탈출조건을 만들었다.
1. graph에서 해당 위치가 1인 경우
2. graph에서 해당 위치가 0이지만 이미 방문처리가 되어있는 경우
BFS 알고리즘의 시작 노드를 graph에서의 모든 점을 시작노드로 잡았다.

from collections import deque

N,M=map(int,input().split())

graph=[list(input()) for _ in range(N)]
visited=[[False]*M for _ in range(N)]
ans=0

def BFS(graph,start_i,start_j):
    if graph[start_i][start_j]=='1' or visited[start_i][start_j]==True:
        return 0

    queue=deque([(start_i,start_j)])
    visited[start_i][start_j]=True
    grad_i=[-1,1,0,0]
    grad_j=[0,0,-1,1]

    while queue:
        cur_i,cur_j=queue.popleft()

        for di,dj in zip(grad_i,grad_j):

            next_i=cur_i+di
            next_j=cur_j+dj

            if next_i>=N or next_j>=M or next_i<0 or next_j<0:
                continue

            if graph[next_i][next_j]=='0' and visited[next_i][next_j]==False:

                visited[next_i][next_j]=True
                queue.append((next_i,next_j))
    
    return 1

for i in range(N):
    for j in range(M):
        ans+=BFS(graph,i,j)

print(ans)

0으로 이루어진 영역 자체에 넓이 제한 조건이 없기 때문에 일단 한번이라도 queue에 시작노드가 들어가게 되면, (0으로 된 면적이 딱 1칸인 경우) 무조건 1을 return할 수 있게 설계했다.

start_i 와 start_j 에 해당하는 위치의 graph값이 1인 경우 혹은 이미 방문처리가 되어있는경우 아예 BFS 알고리즘이 돌지 않게끔 0을 반환하며 함수를 종료했다.

di,dj를 사용해 상하좌우로 이동하며 해당 위치가 graph에서 0에 해당하고 미방문 상태라면 visited에서 해당 위치를 True로 변경한 후, queue에 enque해 인접한 노드를 우선시하여 방문하는 BFS알고리즘을 구현했다. 예시로 시작 노드가 0,0인 경우와 0,1인 경우는 아래와 같이 차례대로 동작하게 된다.

• graph
  

• BFS(graph,0,0)
  
  (i,j)를 기준으로 BFS 탐색은 상하좌우 순서로 탐색을 진행한다. (di,dj)

graph에서 0일 경우 visited에서 해당 위치를 True처리하면서 queue에 넣어준다. BFS 알고리즘을 모두 수행하면 5번과 같은 visited 상태가 된다. 그 후, 더이상 인접한 위치에 0이면서 visited=False인 위치가 없기 때문에 BFS 알고리즘 수행을 중단한다.

• BFS(graph,0,1)
  

시작노드가 (0,0) 일때 BFS알고리즘을 수행해 이미 (0,1)에 해당하는 위치가 visited처리가 되어있어 BFS알고리즘을 수행하지않고 count하지 않게 된다. 이런 방식으로 고립되어있는 0으로 된 영역을 count해 만들 수 있는 아이스크림의 갯수를 셀 수 있다.

• 입출력 예시 1번 수행 결과
  
  3개로 count했다

• 입출력 예시 2번 수행 결과
  
  8개로 count했다.