[백준/24483/파이썬] 알고리즘 수업 - 깊이 우선 탐색 5 (dfs,Python)

[백준/24483/파이썬] 알고리즘 수업 - 깊이 우선 탐색 5 (dfs,Python)

24483번: 알고리즘 수업 - 깊이 우선 탐색 5 (acmicpc.net)

 

코드

from sys import stdin,setrecursionlimit
input = stdin.readline
N, M, R = map(int, input().split()) # 정점, 간선, 시작라인
setrecursionlimit(N+10)
# 방문 순서, 깊이 구하기

visited = [-1] * (N+1) #방문 판단
graph = [[]for _ in range(N+1)] #정점 연결

# -- 입력 및 그래프 연결 -- #
for _ in range(M): # 간선의 이어진 개수만큼이기 때문에
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

for i in range(1, N+1):
    graph[i].sort()

## 깊이 구하는거
## 방문 순서 구하는거
depth = 0
count = 0
# 깊이 * 방문순서 넣기
result = 0
def dfs(graph, visited, start, depth):
    global count, result
    count += 1 ## 방문하기
    visited[start] = count * depth
    result += visited[start] # 결과 넣기
    for i in graph[start]:
        if visited[i] == -1: ## 아직 방문 안했다면
            dfs(graph, visited, i, depth+1)

dfs(graph, visited, R, depth)

print(result)

풀이

• 이 문제는 (정점의 깊이*정점 방문 순서)를 정점번호당 모두 구한 뒤, 나온 값들을 다 더하면 된다.
• 중요하게 볼 코드는 이것이다.
• dfs를 이용한다.

def dfs(graph, visited, start, depth):
    global count, result
    count += 1 ## 방문하기
    visited[start] = count * depth
    result += visited[start] # 결과 넣기
    for i in graph[start]:
        if visited[i] == -1: ## 아직 방문 안했다면
            dfs(graph, visited, i, depth+1)

• depth를 이용하여 dfs에서 트리의 깊이를 구하고, count를 이용하여 방문 순서를 구한다.
• result 변수에 depth * count를 한 값을 다 넣어주면, 자동으로 나온 값들을 더하게 된다.

 

참고

• dfs 자세한 설명은 밑의 링크에 정리해놨다. 

[백준/24480/파이썬(Python)] dfs, 알고리즘 수업 - 깊이 우선탐색2 (tistory.com)

[백준/24480/파이썬(Python)] dfs, 알고리즘 수업 - 깊이 우선탐색2