[TIL][240802] 문제 풀이로 알아보는 BFS, DFS

어떤 문제가 있었나?

1. 입력

백준 1260: DFS와 BFS 문제를 활용하여 DFS, BFS를 구현해 봤다. 구현력의 문제인지 입력부터 막혔다. 그래프가 딕셔너리일 경우 알고리즘을 구현하는 법을 배웠기 때문에 딕셔너리로 입력을 받아야 하는데, 주어진 예시 입력으로 딕셔너리를 만들 아이디어가 떠오르지 않았다.

 

2. 방문 리스트

수업 내용에 구현했던 것처럼 방문 리스트를 만들고 노드가 스택이나 큐에 들어갔었는지 확인하는 과정을 구현했다. 정점의 수만큼 0을 채운 방문 리스트를 만들어 노드가 스택에 들어가면 1로 바꿀 수 있을 것이다. 하지만 dfs는 출력이 잘 되는 반면, bfs는 출력이 되지 않았다. 

 

3. DFS 구현(스택+행렬)

세션에서 dfs를 스택과 반복문을 이용하여 구현을 했으므로 이 문제에도 stack을 이용하여 구현을 해보려 노력했다. 이 전에 했던 구현은 '문자열로 된 딕셔너리'를 이용하는 것이라 행렬을 이용하여 조건문을 작성하려니 잘 생각이 나지 않았다. 방문 리스트가 0이고, 그래프(행렬)가 1이면 stack에 넣는 건데 왜 이렇게 생각이 안 나는지... 구현력은 많이 풀어야 성장한다 하지만 너무 답답하다.

---

어떻게 해결됐는가?

1-1. 입력(행렬)

슈도코드를 작성하여 트리에서 배웠던 행렬로 입력을 받아 그래프를 구현을 시도했다. 정점의 개수 N, 간선의 개수 M, 탐색 시작 정점을 V라 했을 때  입력을 작성하였다. 다음으로 0이 N+1만큼 2차원 배열을 만들어 그래프의 틀을 만들고, 간선을 의미하는 예제를 입력받아 해당 인덱스를 1로 바꿔준다. (0: Falsy, 1: Truthy)

import sys

sys.stdin = open('input.txt', 'r')
N, M, V = map(int, input().split())
graph = [[0] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
    x, y = map(int, input().split())
    graph[x][y] = 1
    graph[y][x] = 1
"""
   0  1  2  3  4
0 [0, 0, 0, 0, 0]
1 [0, 0, 1, 1, 1]
2 [0, 1, 0, 0, 1]
3 [0, 1, 0, 0, 1]
4 [0, 1, 1, 1, 0]
edge == 1
"""

 

1-2. 입력(딕셔너리)

공교롭게도 스쿼드 시간에 같은 문제 풀이를 할 수 있었다. 수업에서는 딕셔너리로 구현을 했는데 너무 쉽게 되어서 당황스러웠다. 먼저 빈 딕셔너리를 만들고, 정점의 개수만큼 key와 value를 만들어 준다. 다음으로 간선을 의미하는 정점들을 각각 key와 value로 넣어준다. 양방향 그래프이기 때문에 반대로도 넣어준다. 그러면 아래와 같이 딕셔너리 형태로 입력을 받을 수 있다.

import sys

sys.stdin = open('input.txt', 'r')
N, M, V = map(int, input().split())
graph = {}
for v in range(1, N+1):
    graph[v] = []
for _ in range(M):
    start_v, end_v = map(int, input().split())
    graph[start_v].append(end_v)
    graph[end_v].append(start_v)
for k, v in graph.items():
    print(f"{k}: {v}")
"""
graph = {
1: [2, 3, 4]
2: [1, 4]
3: [1, 4]
4: [1, 2, 3]
}
"""

 

2. 방문리스트

문제는 방문 리스트를 초기화시켜줘야 했다. dfs 함수를 거쳐가는 동안 방문 리스트는 [0, 1, 1, 1, 1]이 되었으므로 bfs 값은 잘못된 방문 리스트로 인해 결괏값이 나오지 않았던 것이다. 내 해결책은 방문 리스트를 dfs용, bfs용으로 나눈 것이다.

visited_dfs = [0] * (N + 1)
visited_bfs = [0] * (N + 1)

 

3-1. DFS 구현(스택+행렬)

딕셔너리와 다르게 행렬은 인덱스를 이용하여 해당 값을 찾아야하므로 방문 리스트가 0이고, 그래프(행렬)가 1인 조건을 인덱스로 구현했다.

def iterative_dfs(V):
    visited_dfs[V] = 1  # 방문으로 놓고 시작
    stack = [V]
    while stack:
        hand_v = stack.pop()  # 방문 노드 제거
        print(hand_v, end=' ')
        for i in range(1, N + 1):
            if graph[V][i] == 1 and visited_dfs[i] == 0:
                stack.append(i)
                visited_dfs[i] = 1

 

3-2. DFS 구현(스택+딕셔너리)

스쿼드에서 스택과 딕셔너리를 이용하여 풀이를 했다. 행렬로 했을 때는 '작은 정점번호 부터'라는 조건을 맞출 수 없었는데 딕셔너리를 이용한 풀이는 가능해서 놀라웠다. 로직은 비슷했다.

def iterative_dfs(graph, start_v):
    visited = []
    stack = [start_v]
    while stack:
        hand_v = stack.pop()
        if hand_v not in visited:
            visited.append(hand_v)
            for v in sorted(graph[hand_v]):
                stack.append(i)
    return visited

 

3-3. DFS(재귀+행렬)

스택과 행렬을 이용한 DFS는 문제가 원하는 답을 내놓지 못했다. 예를 들어 1을 스택에서 pop()하고 스택에 2, 3, 4가 쌓이게 되는데, 다음 차례의 pop()은 4가 되기에 문제의 조건인 '작은 정점 번호부터'을 위반해 버린다. 그래서 재귀와 행렬을 이용하여 다시 풀어봤다. 재귀를 이용한다면 '작은 정점 번호부터'라는 조건을 해결할 수 있었기 때문이다.

def recursive_dfs(V):
    # visited.append(V)
    visited_dfs[V] = 1
    print(V, end=' ')
    for i in range(1, N + 1):
        if graph[V][i] == 1 and visited_dfs[i] == 0:
            recursive_dfs(i)

 

3-4. DFS(재귀+딕셔너리)

하지만 재귀와 딕셔너리를 사용했을때 출력이 작은 수로 나오지 않는 경우가 생겼다. 이때 value값을 정렬해 주 sorted() 메서드를 사용하면 작은 수부터 순회가 되는 것을 확인할 수 있었다.

def recursive_dfs(graph, visited, start_v):
    curr_v = start_v
    if curr_v not in visited:
        visited.append(curr_v)
        for v in sorted(graph[curr_v]):
            dfs(graph, visited, v)

---

새로 알게 된 점은 무엇인가?

그래프 순회

그래프 순회란 그래프 탐색이라고도 불리우며 그래프의 각 정점을 방문하는 과정을 말한다. 순회를 통해서 주어진 그래프와 특정 정점에 도달 가능한 모든 정점을 찾을 수 있다.

 

그래프를 표현하는 방법은 크게 인접 행렬(Adjacency Matrix)과 인접 리스트(Adjacency List), 2가지 방법이 있다.

https://algorithmtutor.com/Data-Structures/Graph/Graph-Representation-Adjacency-List-and-Matrix/

DFS vs BFS

DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)는 그래프나 트리를 탐색하거나 검색하는데 사용되는 두 가지 기본 알고리즘이다. 이는 미로 찾기를 풀기 위한 전략에서 비롯되었다.

https://www.geeksforgeeks.org/difference-between-bfs-and-dfs/

DFS Depth-First Search 깊이 우선 탐색

스택 구조를 사용하여 먼저 방문한 정점을 스택에 푸시하고, 정점이 없으면 방문한 정점을 팝한다.

• Stack 자료구조를 사용한다. ➡️ LIFO
• 루트 노드에서 시작하며 가능한 한 노드를 거쳐 근처에 방문하지 않는 노드가 없는 노드에 도달할 때까지 탐색하는 방법이다.
• 트리를 만들 때 서브 트리를 하나씩 구성한다.
• 소스 외부에 솔루션이 있는 경우에 사용하면 적합하다,

BFS Breath-First Search 너비 우선 탐색

그래프의 최단 경로를 찾는 정점 기반 탐색법이다. FIFO 방식을 따르는 큐 데이터 구조를 사용한다. BFS에서 정점 하나를 방문하고 표시한 다음 인접한 정점을 방문하여 큐에 저장한다. DFS 보다 느리다.

• 최단 경로를 찾기 위해 Queue 자료 구조를 사용한다 ➡️ FIFO
• 다음 레벨로 넘어가기 전에 동일 레벨의 모든 노드를 통과하는 횡단적 접근 방식이다.
• 트리를 만들 때 레벨별로 구성한다.
• 주어진 소스에 더 가까운 정점을 탐색하는데 적합하다.

---

무엇을 느꼈고 내일은 무엇을 할까?

알고리즘 구현은 항상 어렵다. '어떻게 하면 구현을 하면서 공부할 수 있을까?'라는 질문에 어느 정도 답변이 된 하루였다. 문제를 통해서 구현을 해보니 어느 부분까지 생각을 했는지 혹은 생각이 미치지 못했는지를 알 수 있었다.

다음 주는 기술면접을 대비해 CS와 SQL을 다시 공부해볼까 한다.