[BOJ / 백준] 11724번 연결 요소의 개수 파이썬(Python) 문제 풀이

문제

 

문제 링크 : https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

 

 

 

 

CODE

from collections import deque
import sys

input = sys.stdin.readline


def bfs(v, edges, visited):
    q = deque([v])
    visited[v] = True

    while q:
        now = q.popleft()

        for e in edges[now]:
            if not visited[e]:
                q.append(e)
                visited[e] = True


n, m = map(int, input().split())
edges = [[] for _ in range(n + 1)]
for _ in range(m):
    u, v = map(int, input().split())
    edges[u].append(v)
    edges[v].append(u)

result = 0
visited = [False] * (n + 1)

for i in range(1, n + 1):
    if not visited[i]:
        result += 1
        bfs(i, edges, visited)

print(result)

 

 

 

 

 

풀이

💡 idea

- BFS로 풀이

- 방문하지 않은 노드에 대해 연결된 노드 방문 처리

 

 

💡 implementation

❌ 큐에 노드를 넣으면서 방문처리를 해줬어야 되는데, 큐에서 꺼낼 때 방문처리를 해서 시간초과가 계속 떴었다 😥

    * 방문처리가 되지 않은 채로 큐에 들어가, 중복적으로 큐에 들어갈 수 있어진다

    * 바이러스 문제에서도 이 실수를 했는데, 테스트케이스가 한정적이라 문제가 없었다 (지금은 수정함!)

      이번 문제와 바이러스 문제는 매우 유사하니 복습 차원에서 풀어봐도 좋을 것 같습니다 🙌

      https://codesyun.tistory.com/290

[BOJ / 백준] 2606번 바이러스 파이썬(Python) 문제 풀이

 

 

 

 

 

 

 

결과