[TIL] 99클럽 코테 스터디 4일차 TIL - DFS: 백준 24479 알고리즘 수업 - 깊이 우선 탐색 1 문제 풀이 with python

Today's keyword : DFS

  DFS(깊이 우선 탐색)는 그래프 탐색 알고리즘 중 하나로, 가능한 깊게 노드를 탐색한 후, 더 이상 갈 수 없게 되면 마지막 분기점으로 돌아가서 다른 경로를 탐색하는 방식입니다. DFS는 스택을 사용하여 구현할 수 있으며, 재귀적으로도 구현할 수 있습니다.

문제 설명

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

백준의 "DFS와 BFS" 문제(문제 번호: 24479)는 그래프 탐색 알고리즘 중 깊이 우선 탐색(DFS)을 구현하는 문제입니다. 주어진 그래프에서 특정 시작 정점으로부터의 방문 순서를 출력하는 것이 목표입니다.

입력

• 첫 번째 줄에 정점의 수 n, 간선의 수 m, 시작 정점 r이 주어집니다.
• 다음 m개의 줄에는 간선 정보가 주어지며, 각 줄은 두 정점 a와 b를 나타냅니다. 이는 a와 b가 연결되어 있음을 의미합니다.

출력

• 각 정점에 대해 방문 순서를 출력합니다. 방문하지 않은 정점은 0으로 표시합니다.

예제 

 

문제풀이

import sys
sys.setrecursionlimit(10 ** 6)  # 재귀 깊이 제한 설정
input = sys.stdin.readline  # 입력을 빠르게 받기 위한 설정

# 정점의 수, 간선의 수, 시작 정점 입력
n, m, r = map(int, input().split())
# 인접 리스트 초기화 (1부터 n까지 사용하기 위해 n+1 크기로 생성)
graph = [[] for _ in range(n + 1)]
# 방문 순서를 저장할 리스트 초기화 (0이면 방문하지 않음)
visited = [0] * (n + 1)

# 방문 순서를 기록할 변수 초기화
visit_order = 1

def dfs(graph, v, visited):
    global visit_order
    visited[v] = visit_order  # 현재 정점을 방문했음을 기록
    visit_order += 1  # 다음 방문 순서 증가

    # 현재 정점 v의 인접 정점들을 순회
    for neighbor in graph[v]:
        if visited[neighbor] == 0:  # 방문하지 않은 정점인 경우
            dfs(graph, neighbor, visited)  # 재귀적으로 DFS 호출

# m개의 간선 정보 입력받기
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)  # a에서 b로의 간선 추가
    graph[b].append(a)  # b에서 a로의 간선 추가 (양방향)

# 각 정점의 인접 리스트를 오름차순으로 정렬
for i in range(1, n + 1):
    graph[i].sort()

# DFS 탐색 시작
dfs(graph, r, visited)

# 각 정점의 방문 순서 출력 (1부터 n까지)
for i in range(1, n + 1):
    print(visited[i])

이 문제는 DFS를 사용하여 그래프를 탐색하고, 각 정점의 방문 순서를 기록하는 방식으로 해결합니다.

1.그래프 초기화

• n, m, r을 입력받아 정점 수, 간선 수, 시작 정점을 설정합니다.
• 인접 리스트 형태로 그래프를 표현하기 위해 graph 리스트를 초기화합니다.
• visited 리스트를 초기화하여 각 정점의 방문 순서를 저장합니다.

2. DFS 구현

• DFS 함수 dfs(graph, v, visited)를 정의합니다. 이 함수는 현재 정점 v를 방문하고, 인접한 정점들을 재귀적으로 방문합니다.
• 방문할 때마다 visited[v]에 현재 방문 순서를 기록합니다.

3. 간선 정보 입력

• m개의 간선 정보를 입력받아 그래프에 추가합니다. 양방향 간선이므로 두 정점 모두에 대해 연결을 추가합니다.

4. 정점 정렬

• 각 정점의 인접 리스트를 오름차순으로 정렬하여, DFS 탐색 시 정점이 작은 순서대로 방문되도록 합니다.
• graph : [[], [4, 2], [1, 3, 4], [2, 4], [1, 2, 3], []] -> [[], [2, 4], [1, 3, 4], [2, 4], [1, 2, 3], []]

5. DFS 호출 및 결과 출력

• 시작 정점 r에서 DFS를 호출하고, 각 정점의 방문 순서를 출력합니다.

 

 

 

 

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL