백준[24479] - 알고리즘 수업 (깊이 우선 탐색 1)

 

 

문제

24479번: 알고리즘 수업 - 깊이 우선 탐색 1

 

 

 

작성한 코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

N, M, R = map(int, input().split())
graph = [[] for _ in range(N+1)]
visited = [0] * (N+1)
order = 1

for _ in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

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

def dfs(v):
    global order
    visited[v] = order

    for i in graph[v]:
        if visited[i] == 0:
            order += 1
            dfs(i)

dfs(R)

for i in range(1, N+1):
    print(visited[i])

cf.) 깊이 우선 탐색 → Stack / 재귀함수 사용!

cf.) 재귀의 깊이를 수동으로 늘리기 위해서 sys.setrecursionlimit(10**6) 을 사용해준다.

       → 파이썬에서 재귀의 기본 깊이 : 1000 밖에 되지 않는다.

 

- N : 정점 수 / M : 간선 수 / R : 시작점 / order : 순서를 나타내는 변수

- graph : 연결 정보 리스트 / visited : 방문 순서 리스트

- graph & visited 에서 N+1을 사용한 이유? → 노드 번호와 인덱스를 맞추기 위해서!

- 간선 수 만큼 for문을 돌려 노드 별 연결된 정보를 공백을 기준으로 입력받고, 리스트 graph에 연결 정보를 추가해준다.

- 이후에 리스트 graph를 오름차순으로 정렬해준다.

 

- dfs 함수를 선언

   → dfs를 실행할 때마다 visited에 몇 번째로 방문했는지 값을 저장한다.

   → dfs 실행 후에 변수 order의 값을 +1씩 해주어 방문 순서를 나타낸다.

       cf.) global : 전역 변수

- 최종적으로 인덱스 1부터 N까지의 visited의 값을 출력한다. (0번 인덱스는 제외)