[BOJ 24480] 알고리즘 수업 - 깊이 우선 탐색 2

Depth First Search

[BOJ 24480] 알고리즘 수업 - 깊이 우선 탐색 2

문제

구조화

• 노드의 개수 N, 노드 간 관계인 Edge의 개수 M, Start Node R 정의
• 주의할 점은, 무방향 그래프이기에 양쪽 Edge를 모두 추가하는 형식으로 Graph 구현
• 방문 처리를 위한 State 생성
• 또한, DFS이되 이번엔 내림차순으로 방문하게 되므로 연결 리스트의 Element를 내림차순으로 정렬
• 호출 순서를 의미하는 cnt변수를 정의하여 방문 처리 시 1이 아닌, cnt를 할당
• R인 시작노드를 기준으로 탐색 시작

예제 시각화

해답

import sys
sys.setrecursionlimit(150000)
input = sys.stdin.readline

n,m,r = map(int, input().split())
graph = [[] for i in range(n+1)]
state = [0 for i in range(n+1)] # 방문 처리용
cnt=1 # 탐색 순서변수 cnt에 1을 할당

for i in range(m): # 무방향 그래프
    u,v = map(int, input().split())
    graph[v].append(u) # 왼쪽
    graph[u].append(v) # 오른쪽

for j in graph:
    j=sorted(j, reverse=True) # 내림차를 위해 Reverse


def recur(node):
    global cnt # 함수 내에서 변수 활용을 위한 Global 선언
    state[node] = cnt # cnt를 활용해 방문 순서를 저장
    for nxt in sorted(graph[node], reverse=True): 
        if state[nxt]==0: # 방문하지 않은 노드라면?
            cnt+=1 # 다음 호출 전 cnt에 1을 가산
            recur(nxt)

recur(r) # 시작지점인 r부터 호출
for ans in range(1,len(state)): # 출력
    print(state[ans])