[graph] DFS 기본 구현

문제

접근방법

• 깊이 우선 탐색의 기본 알고리즘 구현
• 방향을 확인해보니 무방향 그래프이고 정점은 7개, 간선은 8개이다.
• 간선 정보는 1 2 1 3 2 4 2 5 4 6 5 6 6 7 3 7
• 시작 정점은 1이다.
• 1) 인접 행렬 또는 2) 인접 리스트로 받아올 수 있다.
• DFS 경로이므로 1) 재귀를 사용하거나 2) 반복문과 스택(pop메서드) 사용할 수 있다.

 

✅  인접행렬 + 재귀로 구현

1-2-4-6-5-7-3

import sys
sys.stdin = open('input.txt')
from collections import deque

V, E = map(int, input().split()) # 7, 8
edge = list(map(int, input().split())) # [1, 2, 1, 3, 2, 4, 2, 5, 4, 6, 5, 6, 6, 7, 3, 7]


# 인접 행렬을 만든다.
graph = [[0]*(V+1) for _ in range(V+1)] # (V+1 * V+1) 행렬
for i in range(E):
    ni, nj = edge[2*i], edge[2*i+1]
    graph[ni][nj] = 1
    graph[nj][ni] = 1  # 무방향 그래프

	# visited 설정한다.
    visited = [False] * (V+1)

# 반복문 함수를 실행한다.
def DFS_recursive(graph, node):
    # 시작 노드를 방문처리한다.
    visited[node] = True
    print(node)

    # 3. 인접한 노드
    for adj_node in range(1, (V+1)):
        if graph[node][adj_node] == 1 and not visited[adj_node]:
            DFS_recursive(graph, adj_node)

# v = 시작노드
DFS_recursive(graph, 1)

 

 

✅  인접행렬 + 반복문 + 스택으로 구현 (python 스타일)

> 방문했던 경로가 아닌 다음 방문가능 경로를 스택에 저장하는 방식, pop할 경우 갈림길까지 점프하듯이 한번에 돌아감.

 

방법 1. 스택 넣고 이후 방문처리

1-3-7-6-5-2-4

import sys
sys.stdin = open('input.txt')

from collections import deque

V, E = map(int, input().split()) # 7, 8
edge = list(map(int, input().split())) # [1, 2, 1, 3, 2, 4, 2, 5, 4, 6, 5, 6, 6, 7, 3, 7]


# 인접 행렬을 만든다.
graph = [[0]*(V+1) for _ in range(V+1)] # (V+1 * V+1) 행렬
for i in range(E):
    ni, nj = edge[2*i], edge[2*i+1]
    graph[ni][nj] = 1
    graph[nj][ni] = 1  # 무방향 그래프


# 스택과 visited 설정한다.
deque_stack = deque()
visited = [False] * (V+1)

# 중복이 발생하는데, 꺼낼때 이미 있으면 패스
# 방문했던 경로가 아닌 다음 방문가능 경로를 스택에 저장하는 방식, pop할 경우 갈림길까지 점프하듯이 한번에 돌아감.
def DFS_repeat_with_stack(graph, node):
    # 시작 노드를 스택에 넣는다. 방문처리 x
    deque_stack.append(node)

    # 스택에 아무 노드가 없을 때까지:
    while deque_stack:
        # 1. 스택 가장 위 노드를 꺼낸다.
        node = deque_stack.pop()
        # 2. 방문하지 않았다면 노드를 방문 표시하고 출력한다.
        if not visited[node]:
            visited[node] = True
            print(node)
            for w in range(1, (V+1)):
                # 3. 인접한 노드이면서 스택에 없는 노드이면
                if graph[node][w] == 1 and not visited[w]:
                    # 4. 스택에 넣는다. (방문체크는 안함)
                    deque_stack.append(w)

DFS_repeat_with_stack(graph, 1)

 

방법 2. 스택과 방문처리를 함께 처리하여 중복을 방지 (코드확인 필요) => 문제는 풀 수 있는데 올바른 경로가 나오지 않음

1-3-7-6-5-4-2

import sys
sys.stdin = open('input.txt')
from collections import deque

V, E = map(int, input().split()) # 7, 8
edge = list(map(int, input().split())) # [1, 2, 1, 3, 2, 4, 2, 5, 4, 6, 5, 6, 6, 7, 3, 7] len=16


# 인접 행렬을 만든다.
graph = [[0]*(V+1) for _ in range(V+1)] # (V+1 * V+1) 행렬
for i in range(E):
    ni, nj = edge[2*i], edge[2*i+1]
    graph[ni][nj] = 1
    graph[nj][ni] = 1  # 무방향 그래프


# 스택과 visited 설정한다.
deque_stack = deque()
visited = [False] * (V+1)

# Push 와 visited 를 묶어 보완. 스택 중복검사할 필요 없고, 스택사이즈를 정점갯수만큼만 만들어도 overflow 되지 않는다.
# 방문했던 경로가 아닌 다음 방문가능 경로를 스택에 저장하는 방식, pop할 경우 갈림길까지 점프하듯이 한번에 돌아감.
def DFS_repeat_with_stack_no_overlap(graph, node):
    # 시작 노드를 방문처리 후 스택에 넣는다.
    visited[node] = True
    deque_stack.append(node)

    # 스택에 아무 노드가 없을 때까지:
    while deque_stack:
        # 1. 스택 가장 위 노드를 꺼낸다.
        node = deque_stack.pop()
        # 2. 기타 처리한다.
        print(node)

        # 3. 인접한 노드들을 모두 보면서
        for w in range(1, (V+1)):
            # 4. 방문한 적 없거 스택에 없는 노드이면

            if graph[node][w] == 1 and not visited[w]:
                # 5. 방문처리 후 스택에 넣는다.
                visited[w] = True
                deque_stack.append(w)

DFS_repeat_with_stack_no_overlap(graph, 1)