[Python] 파이썬 백준(24479) 알고리즘 수업 - 깊이 우선 탐색 1

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

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

---

나의 풀이

입력

첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다.

다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방향 간선을 나타낸다. (1 ≤ u < v ≤ N, u ≠ v) 모든 간선의 (u, v) 쌍의 값은 서로 다르다.

 

출력

첫째 줄부터 N개의 줄에 정수를 한 개씩 출력한다. i번째 줄에는 정점 i의 방문 순서를 출력한다. 시작 정점의 방문 순서는 1이다. 시작 정점에서 방문할 수 없는 경우 0을 출력한다.

 

위의 예제 입력에 따르면 그래프 구조는 다음과 같고 시작 정점이 1이니 DFS 오름차순 기준으로 1 > 2 > 3 > 4 순서로 탐색하게 되며 출력은 위의 예제와 같이 나온다.

---

 

• dict을 통해 그래프를 구현하였으며 양방향 탐색이기 때문에 아래의 코드를 추가함

graph[E1].append(E2)
graph[E2].append(E1)

• 아래의 코드를 통해 아무것도 연결되지 않은 노드에서부터 탐색하는 경우를 예외처리함

if visited_node:
    V = visited_node.popleft()
else:
    pass

---

import sys
from collections import defaultdict
from collections import  deque

N, M, R = map(int, sys.stdin.readline().split())
answer = [0]*N
visited = [False]*N
visited_node = deque([R])
graph = defaultdict(list)
cnt = 1

def DFS(V, graph, R):
    global cnt
    if visited[V-1] == False:
        visited[V-1] = True
        answer[V-1] = cnt
        cnt += 1

        visited_node.extendleft(sorted(graph[V], reverse= True))
        if visited_node:
            V = visited_node.popleft()
        else:
            pass
        DFS(V,graph, R)
        
for _ in range(M):
    E1, E2 = map(int, sys.stdin.readline().split())
    graph[E1].append(E2)
    graph[E2].append(E1)

while visited_node:
    V = visited_node.popleft()
    DFS(V, graph, visited)

answer = list(map(str, answer))
print('\n'.join(answer))

---

다른 사람의 풀이

• dict이 아닌 list로 그래프를 표현함

[[], [4, 2], [1, 3, 4], [2, 4], [1, 2, 3], []]

import sys

sys.setrecursionlimit(10 ** 9) # 재귀 최대 깊이 설정
input = sys.stdin.readline

n, m, r = map(int, input().split())
graph = [[] for i in range(n+1)]
visited = [0] * (n+1) 
count = 1

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)


def dfs(v):
    global count
    visited[v] = count # 다른 풀이

    graph[v].sort()
    for i in graph[v]:
        if visited[i] == 0:
            count += 1
            dfs(i)

dfs(r)

for k in range(1, n+1):
    print(visited[k])