t_음료수얼려먹기_149

문제

n * m
구멍 뚤린부분 0, 칸막이 1
상하좌우 붙어있는경우 연결되어있는 것으로 간주.
얼음의 덩어리 개수가 몇갠가

답

bfs가 더 올바르게 보인다.(복잡도가 더 떨어질듯)

from collections import deque
import sys
arr = []
while True:
    tmp = list(map(int, sys.stdin.readline().strip()))
    if len(tmp)<1:
        break
    arr.append(tmp)
# <span id="yx"></span>y,x
# <span id="상하좌우"></span>상하좌우
ways= [[-1,0],[1,0],[0,-1],[0,1]]
ylimit = len(arr)
xlimit = len(arr[0])
cnt = 0 
# <span id="visit--1"></span>visit = -1
def bfs(y,x):
    q = deque(<a href="/pages/y%2Cx.html" class="wiki-link">y,x</a>)
    while len(q)>0:
        ny,nx = q.popleft()
        arr[ny][nx]=-1
        for way in ways:
            ty = ny + way[0]
            tx = nx + way[1]
            if ty>-1 and tx > -1 and ty < ylimit and tx < xlimit:
                if arr[ty][tx] ==0:
                    q.append([ty,tx])

for y in range(ylimit):
    for x in range(xlimit):
        if arr[y][x] == 0:
            bfs(y,x)
            cnt +=1

print(cnt)