[이취코] 음료수 얼려먹기 / BFS / Python

2차원 배열에서 0은 빈공간, 1은 벽

얼음 개수를 구하는거라 0으로 구성된 묶음이 총 몇 개인지 구하면 됨

 

BFS의 전통적인 문제로... 전설의 문제 '그림'과 같은 형태

 

from collections import deque
n,m = map(int,input().split())

a = [list(map(int,input().strip())) for _ in range(n)]

visited = [[False for _ in range(m)] for _ in range(n)]
dx=[0,0,1,-1]
dy=[1,-1,0,0]
def bfs(i,j):
    q = deque()
    q.append([i,j])
    visited[i][j]=True
    while q:
        cur = q.popleft()
        for k in range(4):
            ax = cur[1]+dx[k]
            ay = cur[0]+dy[k]
            if 0<=ax<m and 0<=ay<n and not visited[ay][ax] and a[ay][ax]==0:
                visited[ay][ax]=True
                q.append([ay,ax])

cnt=0
for i in range(n):
    for j in range(m):
        if a[i][j]==0 and not visited[i][j]:
            bfs(i,j)
            cnt+=1

print(cnt)

 

2중 FOR문 돌면서 배열 내 원소들 다 훑어보는데,

현재 원소가 0이면서 방문한 적 없는 경우에만 탐색 시작함

 

bfs에 들어가면 시작점에서 출발해서 0으로 구성된 상하좌우 원소를 전부 다 탐색하고

더이상 탐색할 q가 없으면 종료