알고리즘 위클리 챌린지 [그래프 탐색2] 문풀

문제는 아래와 같으며

정답 코드 및 문제 요약 해설은

• 문제에서 주어진 조건

: 정점 개수 N

: 간선 개수 M

간선은 단방향

간선 정보:
→ S E 는 S에서 E로만 이동 가능

1번 정점에서 DFS 탐색 시작

DFS로 방문한 정점의 순서를 출력

여기서 말하는 DFS 알고리즘은
DFS (Depth First Search) 깊이 우선 탐색이며,

한 방향으로 끝까지 들어갔다가
더 이상 갈 곳이 없으면 되돌아오는 탐색 방식이다.

아래는 정답 코드

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

from collections import defaultdict

N, M = map(int, input().split())
graph = defaultdict(list)

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

visited = [False] * (N + 1)

def dfs(current):
    visited[current] = True
    print(current, end=' ')
    
    # 핵심: 역순 탐색
    for next_node in reversed(graph[current]):
        if not visited[next_node]:
            dfs(next_node)

dfs(1)

해설 및 주석은 아래 코드

import sys
sys.setrecursionlimit(10**6)   # 재귀 깊이 제한 증가
input = sys.stdin.readline

from collections import defaultdict

# 1. 정점 수 N, 간선 수 M 입력
N, M = map(int, input().split())

# 2. 그래프를 인접 리스트 형태로 저장
graph = defaultdict(list)

# 3. 간선 정보 입력 (단방향)
for _ in range(M):
    s, e = map(int, input().split())
    graph[s].append(e)

# 4. 방문 여부 체크 배열
visited = [False] * (N + 1)

# 5. DFS 함수 정의
def dfs(current):
    # 현재 정점 방문 처리
    visited[current] = True
    
    # 방문 순서 출력
    print(current, end=' ')
    
    #핵심 포인트
    # 인접 정점을 역순으로 탐색
    for next_node in reversed(graph[current]):
        if not visited[next_node]:
            dfs(next_node)

# 6. 1번 정점부터 DFS 시작
dfs(1)