99클럽 코테 스터디 4일차 TIL - 백준 24475번 알고리즘수업 깊이우선탐색1 [Python]

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

 

 

 

 

# 학습 키워드

1. DFS(깊이 우선 탐색)

2. 그래프 탐색

3. 재귀함수

 

 

 

# 문제 접근 방식

DFS를 사용하여 시작 노드에서부터 연결된 노드를 방문 순서에 따라 기록하는 것이 핵심이다. 문제를 해결하기 위해 다음과 같은 접근을 했다.

 

1. 그래프 표현 

노드와 간선 정보를 받아 리스트로 그래프를 표현한다.

 

2. 정렬

시작 노드에서 노드로 갈 때 오름차순으로 탐색해야 하므로 인접 리스트의 각 노드를 정렬한다.

 

3. DFS 구현

재귀를 이용한 DFS를 통해 각 노드를 방문하여, 방문 순서대로 path에 추가하고, 이를 이용해 최종 방문 순서를 기록한다.

 

4. 결과 출력 

각 노드의 방문 순서를 출력 형식에 맞게 result 리스트에 담아 출력한다

 

 

 

# 코드 작성

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)

N, M, R = map(int, input().split())
graph = [[] for _ in range(N + 1)]
path = []
result = [0] * (N + 1)
visited = [-1] * (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, len(graph)):
    graph[i].sort()


def DFS(start):
    visited[start] = 1
    path.append(start)

    for adj_node in graph[start]:
        if visited[adj_node] == -1:
            DFS(adj_node)

    return


DFS(R)

for idx, node in zip(range(1, len(path) + 1), path):
    result[node] = idx

print(*result[1:], sep="\n")

 

 

 

 

# 회고

 

이번 문제를 통해 DFS에 대한 이해를 더 깊게 할 수 있었고, 특히 노드를 방문할 때 오름차순으로 정렬하여 탐색하는 방식이 방문 순서에 큰 영향을 미친다는 점을 알게 되었다.

기존에는 단순히 재귀를 통해 DFS를 구현했었지만, 이번 문제에서는 방문 순서를 기록하기 위해 path와 result 배열을 적절히 활용하는 방법을 배울 수 있어 좋았다.

 

또한  path와 result 배열을 활용해 노드의 방문 순서를 추적할 수 있었던 점이 인상 깊었다. 이 과정에서 DFS의 재귀 호출을 더 잘 이해하게 되었고, 그래프 탐색시 발생할 수 있는 예외 상황들을 고려하는 습관을 길러야 겠다고 생각했다.