<2022모각코/TIL> 코드트리 - 그래프 탐색

저번에 연결요소와 같은 그래프 탐색 문제이다. 백준 풀다가 dfs의 감을 다시 잡기 위해서 기본 개념문제를 풀어보았다. 1에서 부터 탐색을 시행했을 때, 1으로 부터 시작된 서로 다른 연결 요소의 개수를 물어보는 문제.

n, m = tuple(map(int, input().split()))

graph = [
    []
    for _ in range(n + 1)
]
visited = [False] * (n + 1)

for _ in range(m):
    x, y = tuple(map(int, input().split()))
    graph[x].append(y)
    graph[y].append(x)

cnt = 0

def dfs(v):
    global cnt
    visited[v] = True
    for i in graph[v]:
        if visited[i] == False:
            visited[i] = True
            cnt += 1
            dfs(i)
dfs(1)
print(cnt)

우선 저번에 연결 요소 문제와 같이 방향이 없는 그래프임으로 연결 리스트로 다 넣어서

[[], [2, 3], [1, 3], [1, 2], [5], [4]]

이런 형식으로 graph를 형성했다. 그리고 1에서 다른 정점 하나가 이어질 때마다 cnt +=1 을 해주었다.

 

여기서 dfs(v, cnt) 형식으로 넣다보니깐 None값이 뜨길래 global 변수에 대해서 좀 찾아보았다.

 

[Python] 전역 변수 지역 변수 사용법 총 정리/ global, nonlocal