백준 알고리즘 <연결 요소의 개수>

백준 알고리즘 11724번

www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

---

11724번

입력으로 첫 줄에 정점의 수 v와 간선의 수 e가 주어지고 그 다음 e개의 줄 부터 각 간선의 양 끝점이 주어진다.

 

출력으로는 주어진 정보를 토대로 그래프를 그렸을 때 연결 요소의 개수를 구해서 출력하면 된다.

---

문제 해결

BFS와 DFS 중 선택해서 풀면 된다.

 

처음에 DFS로 풀었는데 파이썬 재귀 limit 때문에 런타임 에러가 났다. 그래서 BFS로 고쳤는데!! python 3로 내니까 시간초과가 났다. 질문게시판을 보고 pypy3로 똑같은 코드를 내니까 통과했다!

 

BFS

1) 탐색 시작 노드를 큐에 넣고 방문처리한다.

2) 큐에서 노드(p)를 꺼내 p노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 넣고 방문처리한다.

3) 2)의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

-> 파이썬의 deque를 사용해서 bfs를 구현하였다.

 

각 노드가 방문되었는지 확인하여 방문되지 않았다면 BFS를 수행한다. BFS를 몇 번 수행했는지가 연결요소의 개수이다.

---

코드

from _collections import deque
def main():
    n, m = map(int, input().split())
    data = [[] for i in range(n)]
    visit = [0 for i in range(n)]
    for i in range(m):
        x, y = map(int, input().split())
        data[x-1].append(y-1)
        data[y-1].append(x-1)
    result = 0
    while not all(visit):
        zero = visit.index(0)
        bfs(zero, visit, data)
        result += 1
    print(result)

def bfs(num, visit, data):
    visit[num] = 1
    queue = deque()
    queue.append(num)
    while queue:
        temp = queue.popleft()
        for i in data[temp]:
            if not visit[i]:
                queue.append(i)
                visit[i] = visit[temp]

if __name__ == '__main__':
    main()

---

---