[Backjoon] 24479 알고리즘 수업 - 깊이 우선 탐색 1 Python 문제 풀이

출처:알고리즘 수업 - 깊이 우선 탐색 1

문제해석

1. 1번 노드를 처음 시작하므로 첫번째 방문으로 visited 되었다고 표현하기 위해 isVisited[1]을 1로 바꿈
2. 1번 노드와 연결된 2번, 4번 노드 중에서 2번 노드가 더 작으므로 2번 노드 방문 -> 2번 노드를 2번째로 방문하였으므로 isVisited[2]를 2로 변경
3. 2번 노드와 연결된 1번, 3번, 4번 노드 중 방문하지 않은 노드 중에서 작은 값인 3번 노드 방문 -> 3번 노드를 3번째로 방문하였으므로 isVisited[3]을 3으로 변경
4. 4번 노드와 연결된 1번, 3번, 4번 노드 중 방문하지 않은 노드들이 더 이상 없으므로 재귀 종료. 따라서 5번 노드는 시작 노드 1번으로부터 방문하지 못하는 노드이므로 0으로 명시
5. 출력은 isVisited에 몇번째로 출력되는지를 구한다

주의할 점 방문하는 순서대로가 아니라 몇 번째로 출력되는지(dfs하면서 출력하면 안됨)

• n(정점의 수), m(간선의 수), r(시작 정점 노드), graph(연결 노드 그래프), isVisited(방문 순서 입력 그래프)

1. n, m, r 입력 받기
2. m만큼 graph로 입력받은 후 graph의 배열마다 하나씩 오름차순 sort 정렬
3. dfs 함수 선언 및 재귀 반복, dfs 시작할 때 마다 isVisited에 ans 값 변경 + dfs 실행 후에는 ans 값 1 증가하여 순서대로 값 변경하기
4. isVisted 인덱스 값이 0인 값은 빼고 출력하기

해답코드

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

import sys
sys.setrecursionlimit(10**6) #재귀 허용 깊이를 수동으로 늘려주는 코드

#정점의 수, 간선의 수, 시작 정점
n, m, r = map(int,sys.stdin.readline().split())
#연결노드 그래프 초기화(1번노드와 인덱스 값이 같게 하기 위해서 n+1)
#[[],[],[],[],[]]
graph = [[] for _ in range(n+1)]
#방문 순서 그래프 (위와 같이 인덱스 값과 노드의 값이 동일하게 만들기 위해서 n+1)
isVisited = [0]*(n+1)
#순서 입력
ans = 1

def dfs(graph,start,isVisited):
    #함수 밖의 ans 값을 사용하기 위해서 global 명시
    global ans
    #방문할 떄마다 순서 값 변경
    isVisited[start]=ans
    #연결노드 방문
    for i in graph[start]:
        #방문 안한 노드일 경우
        if not isVisited[i]:
            #순서 증가
            ans+=1
            #dfs 실행
            dfs(graph,i,isVisited)

#연결된 노드 입력 받기
for _ in range(m):
    start, end = map(int, sys.stdin.readline().split())
    graph[start].append(end)
    graph[end].append(start)

#오름차순 정리
for i in range(n+1):
    graph[i].sort()

dfs(graph,r,isVisited)

#순서 출력
for i in range(n+1):
    if i:
        print(isVisited[i])