[알고리즘/백준] 11724번 연결 요소의 개수

11724번 연결 요소의 개수 - https://www.acmicpc.net/problem/11724

Python으로 제출하면 시간 초과 / PyPy3로 제출하면 통과 (메모리 197904KB / 시간 868ms)

 

 

접근 방법

 

- BFS로 품 ( queue 사용)

- 2644번 촌수계산 문제와 마찬가지로 중첩 리스트로 graph를 만들어주고 visited list를 활용하여 queue에 넣어준다.

- sum(visited list) 가 N이 되면 모두 방문했다는 뜻으로 멈춰준다.

 

from collections import deque


def bfs(graph, N):
    visited = [0] * N
    count = 0
    while sum(visited) != N:
        queue = deque([visited.index(0)+1])
        visited[visited.index(0)] = 1
        while queue:
            node = queue.popleft()
            for i in graph[node]:
                if visited[i-1] == 0:
                    queue.append(i)
                    visited[i-1] = 1
        count+=1
    return count

N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]

for i in range(M):
    node1, node2 = map(int, input().split())
    graph[node1].append(node2)
    graph[node2].append(node1)

print(bfs(graph, N))

 

다른 사람의 풀이

 

- 시간초과를 없애기 위해서 input() 함수 대신 readline을 사용 가능

- visited list를 함수에서 선언하지 않고 미리 선언한 후에 반복문을 돌면서 방문하지 않았다면

  bfs 함수를 돌리는 방법도 있음

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