그래프, DFS, BFS

1. 그래프의 표현 방법

그래프는 인접행렬, 인접리스트로 구현할 수 있다. 인접행렬은 구현은 쉽지만 그래프의 탐색, 이후 그래프 알고리즘에 적용하면 효율이 매우 나빠진다. 따라서 인접리스트로 구현하도록 한다.

그러나, 코딩테스트에서 언제 인접리스트로 다 구현할 것인가?
인접리스트를 흉내낼 수 있는 자료구조로 대체하자!
C++에서는 vector, python에서는 dictionary를 이용한다.

C++의 vector를 배열로 선언하고, 각 인덱스를 src로 생각하고, 해당 인덱스에 push_back으로 dst를 삽입하면 인접리스트과 동일하다.

#include <iostream>
#include <vector>
#define MAX 101
using namespace std;

int main() {
	....

	vector<int> v[MAX];

	// src: source
    	// dst: destination
	v[src].push_back(dst); 
	v[dst].push_back(src); // 양방향 그래프라면 양쪽 연결
	
	...
}

2. DFS, 깊이 우선 탐색

노드를 추가하고, 그 노드에서 다음 level의 노드로 확장한다.
그림에서, 1-2-3-4까지 방문한 후에 이전 노드로 돌아가야 하는데 어떻게 할 것인가? '이전으로 돌아간다'는 스택을 이용하여 반복문을 돌린다. 만약 함수로 구현한다면, 함수 역시 스택으로 구성되어있기 때문에 재귀함수로 구현할 수 있다.
탐색 깊이 제한을 둘 수 있는데 알고리즘 문제풀이에서 이는 컴퓨터의 스택메모리의 제한으로 둔다.

// C++ code
void dfs(int start) {
	visit[start] = 1;
	printf("%d ", start);
	for (int i = 0; i < v[start].size(); i++) {
		int next = v[start][i];
		if (!visit[next]) {
			dfs(next);
		}
	}
}

# python code
def DFS(G, start, visit = []):
    visit.append(start)
    for next in G[start]:
        if next not in visit:
            DFS(G, next, visit)
    print(visit)
    return

3. BFS, 너비 우선 탐색

노드를 방문한 후, 인접 노드로 확장한다. 더이상 방문하지 않은 노드가 없을 때 까지 반복한다.
인전 노드로 확장한다 -> 큐 자료구조를 이용한다.

// C++, include <vector>, <queue>, using namespace std
void bfs(int start) {
	queue<int> q;
	q.push(start);
	visit[start] = 1;
	printf("%d ", start);
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		for (int i = 0; i < v[cur].size(); i++) {
			int next = v[cur][i];
			if (!visit[next]) {
				q.push(next);
				visit[next] = 1;
				printf("%d ", next);
			}
		}
	}
}

# python code
def BFS(G, start):
    q = [start]
    visit = [start]
    while q:
        cur = q[0]
        del q[0]
        for next in G[cur]:
            if next not in visit:
                q.append(next)
                visit.append(next)
    print('Result of BFS: ', visit)
    return

파이썬에서 BFS 시간 줄이기

1. queue를 deque로 구현
2. visit를 list, set으로 구현
   for next in visit대신에
   visit[next] == 0 으로 접근하여 O(1)로 한다.

from collections import deque
def BFS(G, start):
	# Queue를 deque로 구현
    q = deque()
    q.append(start)
    
    # visit를 set 또는 1/0 리스트로 만들기
    visit = [0] * (N + 1)
    visit[start] = 1
    
    while q:
        cur = q.popleft()
        for next in G[cur]:
            if visit[next] == 0:
                q.append(next)
                visit[next] = 1
    
    return

4. 예제 코드 실행

입력은 생략