[Python] 반복문으로 dfs 구현하기

1. 현재 노드를 스택에 삽입 (visited는 빈 리스트)

2. 스택에서 노드를 꺼낸다.

3. 꺼낸 노드가 방문되지 않았다면 인접 노드를 전부 스택에 넣는다

2, 3 반복

 

def dfs(start_node, graph):
    st = [start_node]
    visited = []
    
    while st:
        v = st.pop()
        # 방문하지 않았다면
        if v not in visited:
            # 방문 처리
            visited.append(v)
            print(v, end=' ')
            # 스택에 넣는다(graph가 오름차순으로 정렬되어 있고, 오름차순으로 방문)
            st.extend(graph[v][::-1])

 

visited = []로 하지 않고

특정 값(0)으로 사용해서 리스트 형식으로 사용해도 된다

def dfs(start_node, graph):
    st = [start_node]
    visited = [0] * (n + 1)  # 방문 체크 배열
    
    while st:
        v = st.pop()
        # 방문하지 않았다면
        if visited[v] == 0:  # 방문하지 않은 경우
            # 방문 처리
            visited[v] = 1
            print(v, end=' ')
            # 스택에 넣는다(graph가 오름차순으로 정렬되어 있고, 오름차순으로 방문)
            st.extend(graph[v][::-1])

---

 

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

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

 

visited로 빈 set 사용

import sys
input = sys.stdin.readline

def dfs(start):
    cnt = 1
    st = [start]
    visited = set()
    res = [0] * (n+1)
    while st:
        node = st.pop()
        if node not in visited:
            visited.add(node)
            res[node] = cnt
            cnt += 1
            st.extend(graph[node])
    for r in res[1:]:
        print(r)    
    
n, m, r = map(int, input().split())
graph = [[] for _ in range(n + 1)]

for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)
    
for g in graph:
    g.sort()
    
dfs(r)

 

visited와 res를 합치기

import sys
input = sys.stdin.readline

def dfs(start):
    cnt = 1
    st = [start]
    visited = [0] * (n+1)
    while st:
        node = st.pop()
        if visited[node] == 0:
            visited[node] = cnt
            cnt += 1
            st.extend(graph[node])
    for r in visited[1:]:
        print(r)    
    
n, m, r = map(int, input().split())
graph = [[] for _ in range(n + 1)]

for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)
    
for g in graph:
    g.sort()
    
dfs(r)

 

---

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

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

 

visited로 빈 set 사용

import sys
input = sys.stdin.readline

def dfs(start):
    st = [(start, 0)]
    visited = set()
    depth = [-1] * (n+1)
    
    while st:
        node, dep = st.pop()
        if node not in visited:
            visited.add(node)
            depth[node] = dep
            for v in graph[node][::-1]:
                st.append((v, dep+1))

    for d in depth[1:]:
        print(d)
n, m, r = map(int, input().split())
graph = [[] for _ in range(n + 1)]

for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)
    
for g in graph:
    g.sort()
    
dfs(r)

 

visited와 depth를 합치기

import sys
input = sys.stdin.readline

def dfs(start):
    st = [(start, 0)]
    visited = [-1] * (n+1)
    
    while st:
        node, dep = st.pop()
        if visited[node] == -1:
            visited[node] = dep
            for v in graph[node][::-1]:
                st.append((v, dep+1))

    for d in visited[1:]:
        print(d)
n, m, r = map(int, input().split())
graph = [[] for _ in range(n + 1)]

for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)
    
for g in graph:
    g.sort()
    
dfs(r)