꾸준히 개발하기

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

그래프 내 연결되어 있는 그룹이 몇개인지 묻는 문제다. BFS든 DFS든 돌리면서 방문 정보를 저장해주는 visited 배열에서 False인 요소가 존재하면 그룹 수 +1 해주고 다시 BFS/DFS를 돌리면 되는 문제다. visited 배열의 모든 값이 True가 되면 총 그룹 수를 출력해주면 된다.

나는 BFS로 접근해서 풀었다. 이런식으로 그래프가 끊어져 있을 때 어떻게 풀면 될지 고민헀는데 이 문제같은 경우에는 노드 번호가 1부터 N까지 정해져 있어서 수월했다. 

코드는 다음과 같다.

import sys

input = sys.stdin.readline

from collections import deque


def bfs(start):
    visited[start] = True
    queue = deque()
    queue.append(start)

    while queue:
        x = queue.popleft()
        for y in graph[x]:
            if not visited[y]:
                visited[y] = True
                queue.append(y)


N, M = map(int, input().split(" "))
graph = [[] for _ in range(N + 1)]
visited = [False] * (N + 1)
for _ in range(M):
    u, v = map(int, input().split(" "))
    graph[u].append(v)
    graph[v].append(u)

cnt = 0
for i in range(1, N + 1):
    if not visited[i]:
        cnt += 1
        bfs(i)

print(cnt)

2년동안 발전은 했는데 .. 2년 내내 했으면 눈부신 발전 덕분에 취업을 이미 하지 않았을까 하는 생각이 눈물이 앞을 가리는 문제였다.