[Python] 11724: 연결 요소의 개수

정말 기본적인 그래프 순회문제이다.
나는 이 문제를 BFS로 풀었고 그 결과는 아래 사진과 같이 틀렸습니다 연발이었다.

시간 초과가 나는 부분은 visited를 set으로, input()을 sys.stdin.readline()으로 수정하여 어찌어찌 잡았는데 자꾸 40%대에서 틀렸다고 까버렸다.

BFS 로직 자체는 딱히 문제될 게 없어보였기 때문에 더욱 더 답답했다.

import sys
from collections import deque

visited = set()

def bfs(start_v):
    q = deque()
    q.append(start_v)
    visited.add(start_v)
    while q:
        cur_v = q.popleft()
        for v in graph[cur_v]:
            if v not in visited:
                q.append(v)
                visited.add(v)
    return 1

N, M = map(int, sys.stdin.readline().split())
graph = {}
for i in range(1, N+1):
    graph[i] = []
for i in range(M):
    u, v = map( int, sys.stdin.readline().split() )
    graph[u].append(v)

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

7번을 틀린 결과,,, 정답은 바로 문제에 있었다.
바로 방향 없는 그래프인 것이다. 내 코드를 보면 그래프에 간선을 넣을 때 u 에서 v로 한 방향으로만 넣었다. 이게 문제였던 것이다.

for i in range(M):
    u, v = map( int, sys.stdin.readline().split() )
    graph[u].append(v)
    # graph[v].append(u) -- 을 넣어줘야 방향이 없는 그래프가 됨

뭐가 문제냐하면
만약 정점 1이 2를 가르키고 있고 정점 5 역시 2를 가르고 있다고 치자.
1 -> 2
5 -> 2
그럼 정점 1에서 BFS 한 결과 2는 VISITED에 등록되기때문에 5의 BFS 차례에 2를 방문할 수가 없다. 그래서 2와 5는 이어져있는 그래프(연결 요소)가 아닌 것이 된다.

실패 후 성장

문제를 잘 읽자..