[항해99] 99클럽 코테 스터디 4일차 TIL + DFS(백준 24479)

오늘의 학습 키워드

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

공부한 내용

1. DFS 개념

• 그래프에서 깊이를 우선으로 탐색하는 알고리즘
• 시작 정점에서 다음 분기로 넘어가기 전에, 해당 분기를 완벽하게 탐색해야 함

2. 접근 방법

• DFS의 핵심인 visited를 활용. 현재 정점을 방문 처리 하고 -> 다른 정점을 확인, 그리고 방문 수서 숫자를 늘려주는 것이 핵심

3. 핵심 로직 설명

• visited 배열로 방문 순서 관리
• 인접 리스트를 그래프로 표현(graph = [[] for _ in range(N+1)]
  • 0부터 계산하는 것이 아니니까 N+1
• 오름차순 방문을 해야하기 때문에 그래프를 만들고 sort로 정렬
• 재귀를 통해서 DFS를 구현
• 재귀 깊이 제한을 늘려야지 RuntimeError가 발생하지 않음!

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

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

count = 1

def DFS(graph, v, visited):
    global count 
    visited[v] = count
    
    for i in graph[v]:
        if visited[i] == 0:
            count += 1
            DFS(graph, i, visited)

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()
    
DFS(graph, R, visited)

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

오늘의 회고

DFS의 기초적인 문제였다. visited 배열을 단순히 바문 여부가 아닌 방문 순서를 저장하는 것이기 때문에 count라는 변수를 활용할 수 있도록 하였다. 오름차순 방문을 위한 정렬 과정도 필요하였으며, 문제를 제대로 읽지 않으면 놓칠 수 있는 부분이었다. count 변수를 전역 변수로 설정해야 하는 것도 잊지 않아야 한다. 로컬에서 코드를 돌렸을 때는 테스트 케이스를 정상적으로 수행하였는데 제출하였을 때 런타임오류가 발생하였는데 sys.setrecursionlimit(10**6)을 사용해서 해결해야 한다는 것을 새롭게 알았다.