[백준/24480/파이썬(Python)] dfs, 알고리즘 수업 - 깊이 우선탐색2

[백준/24480/파이썬(Python)] dfs, 알고리즘 수업 - 깊이 우선탐색2 

24480번: 알고리즘 수업 - 깊이 우선 탐색 2 (acmicpc.net)

---

중요하게 볼 점 

• 출력 : i번째 줄에는 정점 i의 방문 순서를 출력한다. 시작 정점에서 방문할 수 없는 경우 0을 출력한다.
• 입력 : 간선의 개수만큼 입력받는다.
• 문제 : 인접 정점은 내림차순으로 방문한다.

 

코드

from sys import stdin,setrecursionlimit
input = stdin.readline



count = 0
def dfs(graph, visited, start):
    global count
    count+=1
    visited[start] = count
    for i in graph[start]: # 그래프 집합에서
        if visited[i] == False: #방문하지 않은 경우,
            
            dfs(graph, visited, i)


# 입력 #
N, M, R = map(int, input().split())
setrecursionlimit(N+10) # 재귀 깊이 늘리기
#---1번 정점부터 시작한다. --#
# 방문한 곳
visited = [False] * (N+1)
#그래프 ( 정점 집합)
graph = [[]for i in range(N+1)]

# -- 연결하기 -- #
for i in range(M): # 간선의 수 만큼 반복
    u,v = map(int, input().split()) # u,v 입력받기
    graph[u].append(v) # u,v 서로 연결
    graph[v].append(u) # u,v 서로 연결

# -- 내림차순 정렬 -- #
for i in range(1,N+1):
    graph[i].sort(reverse=True)


# -- dfs -- #
dfs(graph, visited, R)


for i in range(1, N+1):
    if visited[i] != False :
        print(visited[i])
    else:
        print(0)

 

풀이

• 의사코드대로 dfs를 구현한다. 여기서 dfs할때마다 count를 증가시켜서 바로 visited[] 리스트에 몇번째로 도착했는지에 대한 값 count를 넣어준다.
  • global 키워드를 이용하여, 함수 밖 count를 전역변수(global)로 선언하여 함수 안에서 쓸 수 있도록 받아왔다. 
• setrecursionlimit()를 이용하여 재귀의 깊이를 늘려준다. 
• 정점 연결하기 : graph[u], graph[v] 번째 정점을 각각 연결해준다.
• 내림차순 정렬 : graph[]의 각 리스트를 내림차순 정렬해준다.
• dfs 실행
• 출력 : 1부터 N+1 까지 하여, visited[]함수에서 있는 값이 False이 아니면 출력하고, False이면 0을 출력한다. 

 

---

결과