24479 - 알고리즘 수업 - 깊이 우선 탐색

0. 신세한탄

오랜만에 DFS 공부할 겸 시작한 문제...였지만 쉽지 않은 문제였다. 오기로 참고 하지 않고 할려했지만 나의 얕은지식으로는 부족했다... 그렇게 참고해서 알아본 결과 인접 행렬과 인접리스트를 다시 공부하게 됐고 개념은 이해했지만 아직 완벽한 이해를 하지 못하고 문제를 풀어나갔다.

1. 문제설명

문제링크: https://www.acmicpc.net/problem/24479

2. 정답 코드

import sys
 
n,m,r = map(int,sys.stdin.readline().split()) # 정점, 간선, 시작 정점 입력
graph = [[] for _ in range(n+1)] # 인접리스트 초기화
 
for _ in range(m):
    a, b = map(int,sys.stdin.readline().split())
    graph[a].append(b)  # 무방향 그래프로 정점 두개 삽입
    graph[b].append(a)
 
for i in range(1,n+1):
    graph[i].sort(reverse=True)
 
visited = [0]*(n+1) # 방문한 정점
stack = [r]
cnt = 1 # 방문순서 카운트
    
while stack:
    v = stack.pop() # 방문한 노드 pop()
    if visited[v] != 0:
        continue
    visited[v] = cnt # 방문한 정점(index)의 방문 순서(cnt) 삽입
    cnt += 1
    for w in graph[v]:
        stack.append(w)
 
[print(v) for v in visited[1:]]

3. 분석

1) 무방향 그래프로서 입력 받기

import sys
 
n,m,r = map(int,sys.stdin.readline().split()) # 정점, 간선, 시작 정점 입력
graph = [[] for _ in range(n+1)] # 인접리스트 초기화
 
for _ in range(m):
    a, b = map(int,sys.stdin.readline().split())
    graph[a].append(b)  # 무방향 그래프로 정점 두개 삽입
    graph[b].append(a)

2) 오름차순으로 정렬

for i in range(1,n+1):
    graph[i].sort(reverse=True)

여기서 역정렬한 이유는 리스트의 맨 끝에서부터 값을 가져오기 때문에 역정렬하였습니다

3) 방문한 정점 변수 초기화 및 깊이 우선 탐색

1 2 3 4 5 6 7 8 9 10 11 12 13 14

visited = [0]*(n+1) # 방문한 정점 stack = [r] cnt = 1 # 방문순서 카운트      while stack:     v = stack.pop() # 방문한 노드 pop()     if visited[v] != 0:         continue     visited[v] = cnt # 방문한 정점(index)의 방문 순서(cnt) 삽입     cnt += 1     for w in graph[v]:         stack.append(w)   [print(v) for v in visited[1:]]

cs