[Algorithm] 🚩[백준] 1012 (Feat. BFS, 너비 우선 탐색)

BFS 알고리즘을 이해하기 전에 먼저, 그래프 자료구조를 이해해야 한다.

> 그래프(트리, tree) 탐색

하나의 노드에서 시작해서 다른 노드들을 방문하는 것
그래프는 노드와 간선으로 표현된다.
두 노드가 연결되어 있다면, 두 노드는 인접해 있다라고 말한다.

• 루트 노드 : 부모 노드가 없는 최상위 노드
• 단말 노드 : 자식 노드가 없는 노드
• 크기 : 모든 노드의 개수
• 깊이 : 루트 노드로부터 거리
• 높이 : 깊이의 최댓값
• 차수 : 노드별 간선 개수

> BFS

그래프에서 가까운 노드부터 탐색하는 알고리즘
( <-> DFS, 깊이 우선 탐색 : 그래프에서 가장 멀리 있는(깊숙한) 노드를 우선적으로 탐색하는 알고리즘 )

• 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾을 때 사용
• 큐를 사용해서 선입선출(FIFO) 원칙으로 탐색

> BFS 알고리즘 동작 과정

1. 탐색 시작 노드를 큐에 삽입 후 방문 처리
2. 큐에서 노드를 꺼내 방문하지 않은 인접 노드를 큐에 삽입 후 방문 처리
3. 2번 과정을 끝까지 수행

---

이 문제는 queue를 이용해도 되고, deque를 이용해도 된다.
나는 양쪽에서 append, pop을 할 수 있도록 deque를 이용하였다.

풀이 -> 구역마다 나눠서 생각했다. 한 구역마다 지렁이 1마리가 필요한 것이다. 그래프 각 칸을 돌다가 1인 칸을 발견하면 BFS를 수행한다.
즉, 한 구역에 BFS가 한 번 수행되는 것이다. BFS가 수행되고 나면 그 구역의 1이 모두 0으로 바뀐다. 따라서 지렁이는 BFS가 수행될 때마다 카운트 +1 이 된다.

꼬리의 꼬리를 물어 풀어나가는 것 같다는 느낌이 들었다.

<풀이>

from collections import deque

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

t = int(input())

def bfs(a, b):
    queue = deque()
    queue.append((a, b))
    graph[a][b] = 0

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 1:
                graph[nx][ny] = 0
                queue.append((nx, ny))


for i in range(t):
    cnt = 0
    m, n, k = map(int, input().split())
    graph = [[0]*m for _ in range(n)]

    for j in range(k):
        x, y = map(int, input().split())
        graph[y][x] = 1

    for a in range(n):
        for b in range(m):
            if graph[a][b] == 1:
                bfs(a, b)
                cnt += 1

    print(cnt)

<참고>
그래프 자료구조