필독!!) DFS / BFS 정리 + 인접행렬, 인접리스트

 

이 포스팅을 함께 보자.

https://100won-developer.tistory.com/entry/DFS-BFS-%EC%B0%A8%EC%9D%B4

DFS / BFS 차이

 

BFS, DFS 알고리즘 분석보다는 언제 어떻게 쓰이고, 어떤 개념들이 쓰이는지 적어보았다.

 

DFS

DFS는 그래프깊이 우선 탐색법이다. Root 노드에서 시작하여, 최대한 깊이 탐색한 후 다음 branch로 넘어가는 방법을 말한다.

def DFS(v):
    visited1[v] = True # 현재 노드는 방문한것
    print(v, end=' ') # 방문한 노드 출력
    for i in range(1, n+1):
        if visited1[i] == False and graph[v][i] == 1: # 아직 방문하지 않았고, 연결되어 있는 경우
            DFS(i) # 방문하지 않은 노드 계속 방문

BFS

BFS는 인접한 노드부터 점점 멀리 방문한다.

from collections import deque

def BFS(v):
    queue = deque([v])
    visited2[v] = True # 현재 노드는 방문한것

    while queue: # 큐가 빌때까지 진행
        v = queue.popleft() # 이전에 방문한 노드 꺼냄
        print(v, end=' ')
        for i in range(1, n+1):
            if visited2[i] == 0 and graph[v][i] == 1: # 방문한적 없고, 연결되어있다면
                queue.append(i)
                visited2[i] = 1 # 방문처리

DFS , BFS 비교

	DFS	BFS
모든 노드를 방문	✅	✅
최단경로		✅
사용하는 자료구조	Stack (or 재귀)	Queue
경로의 특징을 저장	✅
대규모 그래프	✅
소규모 그래프 & 시작 지점과 대상 지점이 가까울 때		✅
간단하게 구현	✅
속도		✅

visited 언제 쓸까?? (팁)

문제를 풀다보면, visited를 쓰는 경우도 있고 안쓰는 경우도 있었다. 차이가 무엇이었을까 ???

1. DFS - visited 쓰는 상황 多

DFS는 군집별로 방문했던 곳을 다시 방문하지 않기 때문에 visited를 함께 써서 이전에 방문했는지 체크해주는 것이 좋다. 그래서 DFS 실행 전, graph에 값이 있는지, 그리고 visited 했는지 이렇게 2개 체크한 후 DFS를 실행해주는 경우가 많았다.

 

2. BFS - visited 안써도 가능, 상황별로 쓸 수도 있음.

반면 BFS는 거리, 시간 측면에서 가장 짧은 것을 찾는 경우가 많다. 최단거리/시간을 찾을 땐 방문했던 곳을 다시 방문하는 경우가 당연히 있을 수 있다 !!! 그래서 visited를 굳이 안써도 된다. (어쩌면 안쓰는 게 맞다. 라고 할 수도 있지만 때에 따라 visited가 필요하다고 한다.)

 

그래서 BFS처럼 visited를 안쓸 때는, graph에 직접 시간이나 거리 등을 누적해가는 경우가 많다.

graph[nx][ny] = graph[x][y] + 1 이런식으로 말이다.

 

그래프 구현 방법

DFS, BFS를 구현할 땐 문제에서 주어진 그래프를 초기화해야하는데, 이때 2가지 방법이 있다.

1. 인접 행렬 (Adjacency Matrix)

한마디로 N개의 노드에 대해서 N*N 2차원 행렬을 만들어서 푸는 방법이다. 예시를 보자. 다음 주어진 숫자끼리 이어져있다는 뜻이다.

 

1 2

3 4

2 3

 

이런식으로 연결되어있다고 치자. 그럼 1과 2가 연결되어있으므로 1->2와, 2->1 둘다 연결되어있음을 표시해줘야한다.

 

장점

• 노드끼리 연결되어있는지 간선을 조회할 때 graph[i][j] 이런식으로 O(1)만에 조회할 수 있다.
• 구현이 비교적 간단하다.

단점

• 항상 N^2개의 행렬이 필요하므로 공간복잡도 측면에서 비효율적일 수 있다.
• 이를 초기화 하기 위해 adj[1][2] = True , adj[2][1] = True 이렇게 2번 표기해줘야하는 약간의 번거로움이 있다.
• A 노드에 연결된 모든 노드를 확인하려면, graph[A][0] ~ graph[A][N-1]까지 모두 확인해야해서 O(N)의 시간복잡도를 가진다. 그래서 노드가 많고 간선(연결)이 적을때 비효율적이다.

 

2. 인접 리스트 (Adjacency List)

앞서 인접 행렬은 행렬을 썼듯, 인접 리스트는 리스트를 사용하며 그 중에서도 연결 리스트를 이용한다. 연결 리스트로 각 노드가 어느 노드와 연결되어있는지 표시한다. 0, 1의 연결을 확인하고 싶은 경우 graph[0] 리스트를 순회하여 1번이 있는 지 확인하면 된다. 무방향인 경우 인접 행렬과 동일하게 0, 1이 연결된다면 1, 0의 연결도 추가하여야 한다.

 

장점

• 앞서 인접 행렬은 반드시 N*N 행렬을 만들어야 했는데, 인접 리스트는 그런 과정이 없기에 메모리 관점에서 효율적이다.
• A노드와 연결된 "모든 노드를 확인"하고자 할때 최악의 경우(즉, A노드가 모든 노드와 연결된 경우)는 O(N)이지만, 대부분의 경우 항상 O(N)인 인접행렬보다 빠르다.

단점

• 앞서 인접 행렬에선 간선을 조회할 때가 장점이었는데, 반대로 인접 리스트에선 그것이 단점이다. 즉 간선을 조회할 때 노드의 인접 리스트를 탐색해야해서 시간이 더 걸리게 된다.