백준 - 양 한마리... 양 두마리... 11123번

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

👏 문제 요약

양 무리(붙어있는 # 덩어리를 1로 센다. )의 수를 구하여라.

😘 key point

전형적인 dfs,bfs 문제이다. #모양이 있다면 bfs를 통해 방문했다는 표시를 남긴다면 양의 무리를 쉽게 구할 수 있을 것이다.

🤣 코드

from collections import deque

n = int(input())

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

def bfs(i,j):
    q.append((i,j))
    visited[i][j] = True

    while q:
        y,x = q.popleft()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or ny < 0 or nx >= w or ny >= h:
                continue
            
            if graph[ny][nx] == '.':
                continue

            if visited[ny][nx] == False and graph[ny][nx] == '#':
                visited[ny][nx] = True
                q.append((ny,nx))



for  _ in range(n):
    h,w = map(int, input().split())
    
    graph = [list(map(str, input())) for _ in range(h)]
    visited = [[False] * w for _ in range(h)]     
    count = 0

    q = deque()

    for i in range(h):
        for j in range(w):
            if graph[i][j] == '#' and visited[i][j] == False:
                
                bfs(i,j)
                count += 1

    print(count)