PY-L3-032 / 그래프
연결 요소 수
중급문제
노드 번호 0~n-1의 방향 없는 그래프를 n, edges로 받습니다. 연결 요소 수를 반환하세요. 간선은 두 노드 번호의 배열입니다.
solve(*args) 함수에서 값을 반환하세요. print 출력은 정답 판정에 사용하지 않습니다.
입출력 예시
예제 1
입력: [5,[[0,1],[1,2],[3,4]]] 반환: 2
예제 2
입력: [3,[]] 반환: 3
힌트
아직 방문하지 않은 노드에서 순회를 시작할 때 요소 수를 늘립니다.
해설·정답 보기
반복형 DFS로 같은 연결 성분을 모두 방문 처리합니다. 고립 노드도 하나의 요소입니다.
def solve(n, edges):
graph = [[] for _ in range(n)]
for a, b in edges:
graph[a].append(b)
graph[b].append(a)
seen = set()
count = 0
for root in range(n):
if root in seen:
continue
count += 1
stack = [root]
seen.add(root)
while stack:
for node in graph[stack.pop()]:
if node not in seen:
seen.add(node)
stack.append(node)
return countsolution.py결과 비교
코드는 이 브라우저에 자동 저장돼요.
풀이 결과
코드를 작성하고 채점하기를 눌러보세요.
학습용으로 제공된 조건을 확인해요. 알고리즘 사용 방식·설계 의도는 해설과 함께 비교해보세요.