BOJ11724 연결 요소의 개수

 

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

11724번: 연결 요소의 개수

 

난이도: 실버2

소요시간: 30분

관련 알고리즘: 그래프, dfs, bfs

 

나는 bfs를 이용하여 풀었다.이전에 풀었던 bfs 문제와 비슷하여 30분이내에 풀었다. 15분만에 풀었지만 인덱스를 실수한 부분이 있어 시간이 더욱 걸렸다.

그래프 문제의 경우 입력을 받을 때 인접 리스트로 받으면 편하다. graph[a] =b, graph[b]=a. 이렇게 입력을 받으면 dfs나 bfs, 다익스트라 알고리즘을 사용할 때 매번 반복문으로 인접한 노드를 검색할 필요가 없다.

 

import sys
from collections import deque
N,M = map(int,sys.stdin.readline().split())
graph=[[]for _ in range(N+1)]
visited=[False for _ in range(N+1)]

for _ in range(M):
    node1,node2 = map(int,sys.stdin.readline().split())
    graph[node1].append(node2)
    graph[node2].append(node1)

def bfs(start):

    if visited[start]==True:
        return 0
    deq = deque([start])

    while(deq):
        q= deq.popleft()
        if visited[q] == True:
            continue
        visited[q]=True
        for g in graph[q]:
            deq.append(g)
    return 1


count=0
for i in range(1,N+1):
    count+=bfs(i)
print(count)