[Code Tree][Python] 그래프 상에서의 DFS 탐색

Overview

• 체감 난이도: ★★☆☆☆
• 문제 레벨: 
• 문제 유형: DFS
• 풀이 상태: 답안참고 / 스스로 해결
• 추후: 다시 풀어보기 / 간단 복습 / 완벽 이해 

---

[문제]

https://www.codetree.ai/missions/2/problems/graph-traversal?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

[코드]

1. 그래프 초기화

n, m = map(int, input().split())
arr = [[0] * (n + 1) for _ in range(n + 1)]
visited = [False] * (n + 1)

 

2. 간선 입력 받기 

for _ in range(m):
    v1, v2 = map(int, input().split())
    arr[v1][v2] = 1
    arr[v2][v1] = 1

• arr[v1][v2] = 1, arr[v2][v1] = 1 : 양방향 연결 의미(무방향 그래프)

3. DFS 함수 실행 & 방문한 노드 개수 세기

dfs(1)
result = sum(visited) - 1
print(result)

• visited 배열에서 True로 표시된 모든 노드의 개수를 합산한다. (True는 1로 간주된다._
• 1번 정점도 방문된 상태이므로, -1 을 해서 개수를 제외해준다. 

 

최종 코드(인접 행렬을 활용한 DFS)

def dfs(v):
    visited[v] = True

    # 연결된 노드를 계속 탐색
    for i in range(1, n + 1):
        if arr[v][i] == 1 and not visited[i]:
            dfs(i)

# main
n, m = map(int, input().split())
arr = [[0] * (n + 1) for _ in range(n + 1)]
visited = [False] * (n + 1)

# 간선 입력 받기
for _ in range(m):
    v1, v2 = map(int, input().split())
    arr[v1][v2] = 1
    arr[v2][v1] = 1

# 1번 정점에서 시작하는 DFS 호출
dfs(1)

# 방문한 노드 개수 세기 (1번 자기 자신 제외)
result = sum(visited) - 1
print(result)