코딩테스트/백준
[백준] 11724번 연결 요소의 개수 / 파이썬(python)
Jiwon_C
2021. 5. 25. 22:17
# 문제 링크
https://www.acmicpc.net/problem/11724
11724번: 연결 요소의 개수
첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주
www.acmicpc.net
# Soultion
처음에 dfs를 이용하여 문제를 풀었더니 recursion 에러가 발생하여 재귀깊이를 설정해주었다.
그래도 동일하게 문제가 발생하여 bfs로 풀었더니 동일한 에러가 발생하였다.
알고보니 input()을 받는과정에서 시간초과가 발생하였다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
import sys
from collections import deque
n,m = map(int,input().split())
graph = [[]*n for _ in range(n+1)]
for _ in range(m):
u,v = map(int,sys.stdin.readline().split())
graph[u].append(v)
graph[v].append(u)
visited = [0]*(n+1) # 방문체크
def bfs(n):
queue = deque([n])
while(queue):
n = queue.popleft()
for node in graph[n]:
if visited[node]==0:
queue.append(node)
visited[node]=1
cnt = 0
for i in range(1,n+1):
if visited[i]==0:
bfs(i)
cnt+=1
print(cnt)
|
cs |
6. input()으로 입력값을 받을때, readline()함수로 입력받음
7~8. 각 노드들의 연결정보를 graph라는 리스트에 저장
10. 노드방문 체크를 위한 1차원 리스트 (0으로 초기화)
12. bfs 동작
22. 1부터 n까지의 노드들을 확인
23. 방문하지 않은 노드가있다면 bfs를 이용하여 방문