11724 연결요소의 개수

1. 문제

문제는 링크를 들어가면 볼 수 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

from collections import deque
import sys

def BFS(graph,V,visited):

    visited[V] = True
    q = deque([V])
    # q.append(V)

    while q :
        now = q.popleft()
        for k in graph[now]:
            if not visited[k] :
                visited[k] = True
                q.append(k)

read = sys.stdin.readline
N,M = map(int,read().split())

graph = [[] for _ in range(N+1)]
for i in range(M):
    u,v = map(int,read().split())
    graph[u].append(v)
    graph[v].append(u)

visited = [False]*(N+1)
cnt = 0
for j in range(1,N+1):
    if not visited[j] :
        BFS(graph,j,visited)
        cnt += 1
    else : continue
print(cnt)

3. 문제 풀이

이 문제는 DFS도 가능하고 BFS도 가능하지만, 재귀함수를 쓰면 문제가 발생할 것 같아서 나는 BFS로 풀었다. 아주 기초적인 예제인데.. N과 N+1을 계속 혼동해서 쓰다보니 문제가 생긴다.. 그냥 array[0]을 1번째로 놓고 푸는 연습을 해보자.