[백준 11123번] 양 한마리... 양 두마리...

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

import sys
from collections import deque
input = sys.stdin.readline

t = int(input().rstrip())
    
dx = [-1,1,0,0]
dy = [0,0,-1,1]

for _ in range(t):

    h,w = map(int,input().split())

    answer = 0

    area = [list(input().rstrip()) for _ in range(h)]
    visited = [[False]*w for _ in range(h)]

    def bfs(x,y):

        if visited[x][y] or area[x][y] == ".":
            return False
    
        queue = deque([(x,y)])

        visited[x][y] = True

        while queue:
            temp_x, temp_y = queue.popleft()
            
            for i in range(4):
                nx = temp_x + dx[i]
                ny = temp_y + dy[i]
                
                if 0 <= nx < h and 0 <= ny < w and not visited[nx][ny] and area[nx][ny] == "#":
                    visited[nx][ny] = True
                    queue.append((nx,ny))

        return True
    
    for i in range(h):
        for j in range(w):
            if bfs(i,j):
                answer += 1
    
    print(answer)

 

이번 문제는 DFS/BFS 알고리즘을 활용하여 양(#)무리의 개수를 구하는 문제이다.

 

2차원 배열을 하나씩 순회하면서 탐색해본 결과, 양무리인 경우에 count를 +1 해주는 방식으로 풀 수 있는 간단한 문제이다. 물론 DFS 알고리즘을 사용해도 상관없지만, 본인은 BFS 알고리즘를 사용하여 풀었다.

 

그래프 탐색 알고리즘을 복습할 수 있었던 간단한 문제였다 :)