[BOJ] 24479 - 알고리즘 수업-깊이우선탐색 1

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

https://www.acmicpc.net/problem/24479

문제 정의

---

입력으로 주어지는 간선 정보로 DFS를 수행하고 각 노드의 방문 순서를 출력한다.

접근 방법

---

DFS 알고리즘 활용

문제 해설

---

• 각 노드 정보를 이차원 리스트 정보로 받는다.

• 무방향 그래프 이므로 양방향 간선으로 간주하고 양쪽의 정보를 다 입력한다.

• 시작 노드인 R 부터 DFS를 수행한다.

풀이

---

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

N, M, R = map(int, input().split()) # 정점 개수, 간선 수, 시작 정점

graph = [[] for _ in range(N+1)]    # 연결 그래프 
visited = [False] * (N+1)   # 방문 여부 체크
orders = [0]*(N+1)   # 순서 체크

# 간선 정보 입력
for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

# 오름 차순 정렬
for i in range(1, N+1):
    graph[i] = sorted(graph[i])

cnt = 1
def dfs(start):
    global cnt
    visited[start] = True
    orders[start] = cnt
    for i in graph[start]:
        if not visited[i]:
            cnt += 1
            dfs(i)

dfs(R)

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

정리

---

• DFS의 원래 시간복잡도는 $O(N)$ 이다.

• 이 문제에서 count 변수를 넘겨주는 것 때문에 살짝 오류가 있었다.

• 함수안에 변수를 넘겨줄 땐 global 을 표시해줘야 하는 것을 잊지말자.

Uploaded by N2T