[boj] 백준 11123 양 한마리... 양 두마리... python 풀이

문제

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

11123번: 양 한마리... 양 두마리...

 

문제 풀이

섬의 갯수를 찾는 bfs

 

코드

import sys
input = sys.stdin.readline
import collections

def bfs(MAP):
    visited = [[0 for _ in range(len(MAP[0]))] for _ in range(len(MAP))]
    move = {(-1,0),(0,-1),(1,0),(0,1)}
    total = 0

    for i in range(len(MAP)):
        for j in range(len(MAP[0])):
            if MAP[i][j] == '#' and visited[i][j] == 0:
                total += 1

                # bfs
                q = collections.deque()
                q.append((i,j))
                visited[i][j] = 1

                while q: 
                    cx, cy = q.popleft()

                    for tx, ty in move:
                        nx = tx + cx
                        ny = ty + cy

                        if 0<=nx<len(MAP) and 0<=ny<len(MAP[0]) and MAP[nx][ny] == '#' and visited[nx][ny] == 0:
                            q.append((nx,ny))
                            visited[nx][ny] = 1
    return total

T = int(input().strip())
for _ in range(T):
    H,W = map(int,input().split())
    MAP = [input().strip() for _ in range(H)]

    print(bfs(MAP))