백준 24479번: 알고리즘 수업 - 깊이 우선 탐색 1 [python]

난이도 : 실버 2
유형 : DFS
https://www.acmicpc.net/problem/24479

문제 접근

이 문제를 풀기위해서는 깊이 우선 탐색(DFS)에 대한 개념이 필요하다.
DFS,BFS 개념
에서 간단하게 다루어 보았다. 그러나 다른 포스팅 보며 이해하는 것을 추천한다.

파이썬에서 DFS 재귀 구현 절차는 다음과 같다.
1. 입력값을 정의하거나 입력을 받는다.

• 정점 수, 간선 수, 시작 정점
• 간선 정보

2. 그래프를 인접 리스트로 구성한다.

   • 간선을 양방향(또는 단방향)으로 추가
   • (선택) 방문 순서를 정해주고 싶다면 정렬

3. 방문 여부를 체크할 리스트를 만든다.

4. DFS 함수(재귀)를 정의한다.

   • 현재 노드 방문 처리
   • 연결된 노드 중 방문하지 않은 곳으로 재귀 호출

5. 시작 정점에서 DFS를 호출한다.

이를 통해 코드를 구현해보겠다.

내 코드

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

# 1. 입력값을 입력받는다.
N, M, R = map(int,input().split())
edges = []
for _ in range(M):
    u, v = map(int,input().split())
    edges.append((u, v))

# 2. 입력받은 정보들로 그래프 구성하기
# 2-1. 그래프 구조 초기화
graph = []
for i in range(N + 1): # 0번 인덱스 노드를 사용하지 않기 위해 N+1 처리 해주는 모습
    graph.append([])
#  graph = [
#     [],     # 0번 인덱스 (사용 안함)
#     [],     # 1번 노드의 인접 노드
#     [],     # 2번 노드의 인접 노드
#     [],     # 3번 노드의 인접 노드
#     [],     # 4번 노드의 인접 노드
#     []      # 5번 노드의 인접 노드
# ] 꼴이 됨.

# 2-2. 간선 정보 기반으로 인접 리스트 구성
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u) # 무방향 그래프니까 양방향 연결
  
# graph = [
#     [],        # 0번 (사용 안함)
#     [2, 3],    # 1번 노드 → 2, 3과 연결
#     [1, 4],    # 2번 노드 → 1, 4와 연결
#     [1, 5],    # 3번 노드 → 1, 5와 연결
#     [2],       # 4번 노드 → 2와 연결
#     [3]        # 5번 노드 → 3과 연결
# ] 가 됨.

# ++ 문제에서 인접노드는 오름차순으로 정렬하라고 했다.
for i in range(1 , N+1):
    graph[i].sort()

# 3. 방문 여부를 체크할 리스트를 만든다.
visited = [False] * (N + 1) # 인덱스 0 을 안쓰기 위해 N+1 정의

# ++ 문제에서 원하길 각 정점이 몇 번째로 방문되었는지를 출력해야 한다.
order = [0] * (N + 1)
cnt = 1

# 4. DFS 함수(재귀)를 정의한다.
def dfs(node):
    global cnt
    visited[node] = True
    order[node] = cnt
    cnt += 1

    for neighbor in graph[node]:
        if not visited[neighbor]:
            dfs(neighbor)

# 5. DFS 시작
dfs(R)

# 6. 결과 출력
for i in range(1, N + 1):
    print(order[i])

그래프 꼴

print(graph) #[[], [2, 4], [1, 3, 4], [2, 4], [1, 2, 3], []] 그래프는 각 노드에서 어떤 노드로 뻗어나왔는 지 간선이 들어가있구나. (0번 인덱스 제외)

DFS 개념은 이해했지만 손 코딩 하라고 하면 아직 못하겠다. 나머지 같은 유형의 문제들을 풀며 더 친해져야겠다.