탐색

dfs와 bfs

dfs

def dfs(g, vertex, visited):
    print(vertex, end=' ')
    visited[vertex] = True
    for adj in graph[vertex]:
        if not visited[adj]:
            dfs(g, adj, visited)


# element of graph is sorted ASC
graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visited = [False] * 9

dfs(graph, 1, visited)

bfs

from collections import deque

def bfs(graph, vertex, visited):
    q = deque(str(vertex))
    visited[vertex] = True
    print(vertex, end=' ')

    while q:
        for adj in graph[int(q.popleft())]:
            if not visited[adj]:
                print(adj, end=' ')
                visited[adj] = True
                q.append(adj) 


# element of graph is sorted ASC
graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visited = [False] * 9
bfs(graph, 1, visited)

회고

• graph는 node보다는 vertex로 표현(edge로 연결)
• 그래프의 vertex가 1부터 시작해서 graph의 첫 원소를 비어둔다. 그로 인한 문제로 출력의 마지막에 %이 남는데 코딩테스트라면 주의할 필요가 있다.
• dfs는 스택으로 구현하므로 recursive하게, bfs는 queue를 이용해서
• 그래프의 각 원소들은 오름차순으로 정렬되어 있어야한다.

dfs

반복되는 것
현재 vertex에서 인접한 낮은 번호부터 차례대로 방문하지 않은 vertex를 재귀적으로 접근, 접근하면 방문 리스트에 추가하고 방문한 것을 출력한다. 즉, 함수를 호출하면서 방문.

스택에서 pop하는 경우
현재 vertex에서 인접한 vertex 중, 모두 방문 경우라서 진행할 수 없을 때(for 반복문 끝났을 때)

일반적인 recursion이랑 다른점
재귀 함수를 사용할 때는 끝날 때를 명시하여야만 한다. 하지만 dfs를 구현할 때는 반복문 for가 끝나면 dfs가 자연스럽게 끝나도록 되어있다. 이것을 조절하기 위해서 visited list를 이용한다.

bfs

참고 답안과 차이
deque에는 iteratable한 변수를 넣어서 초기화한다. 정수는 리스트로 바꿔주는 것이 str()로 묶는 것보다 좋다.

반복되는 것
큐에 추가하면서 방문표시를 하지만 큐 자료구조의 특성에 의해 popleft하면서 방문 출력을 해도 된다. 이렇게 하면 초기 vertex의 출력을 생략할 수 있다.(참고 코드를 확인할 것)