오늘 학습 키워드

• 그래프

• unordered_set 해시

그래프

인접행렬로 표현

• 간선이 있을 경우, 행렬에 값으로 가중치를 저장

    const int N = 2; // 노드 수 
    int graph[N][N] = {0}; // 초기화된 인접 행렬

    graph[0][1] = 400; // 서울(0) -> 부산(1)

• 장점: 구현이 쉽고 간선 확인이 배열접근이라 아주 빠름
• 단점: 간선이 적을 경우 메모리 낭비

인접 리스트로 표현

• {Destination, Weight} 형식의 값을 vector로 표현

	struct Node {
      int v;
      int w;
	};

	const int N = 5;
    vector<Node> graph[N];	// 0번째 인덱스는 무시

    graph[1].push_back({2, 3});
    graph[2].push_back({1, 6});
    graph[2].push_back({3, 5});
    graph[3].push_back({2, 1});	// 이후는 생략

• 장점: 메모리 효율적
• 단점: 간선 확인할 때 간선 개수가 K라면 O(K)의 시간복잡도 가짐

그래프 탐색

깊이 우선 탐색 (DFS)

• 스택(재귀함수)를 이용하여 구현 가능

using namespace std;

const int N = 5;
vector<int> graph[N];
bool visited[N];

void DFS(int v) {
    visited[v] = true;

	cout << v << endl;	// v node 처리 

    for (int u : graph[v]) {
        if (!visited[u]) {
            DFS(u);
        }
    }
}

int main() {
    graph[0] = {1, 2};
    graph[1] = {3};
    graph[3] = {4};

    DFS(0);
    return 0;
}

너비 우선 탐색 (BFS)

• 해당 node와 인접한 node들을 먼저 처리하고 다음 단계로 넘어가서 다시 그 노드들과 인접한 노드를 처리

• 큐를 이용하여 구현 가능

• 큐에 넣기 전에는 방문처리를 하고, 큐에서 pop할 때 node처리를 해야함 (순서중요)

using namespace std;

const int N = 5;
vector<int> graph[N];
bool visited[N];

void BFS(int v) {
    queue<int> Q;			// 큐 생성
    visited[v] = true;		// 방문 처리하고
    Q.push(v);				// enqueue

    while (!Q.empty()) {			// 큐 빌 때까지(다 방문할때까지) BFS
        int u = Q.front(); Q.pop();	// pop하는 순간
        cout << u << " ";			// 해당 노드 처리
        for (int w : graph[u]) {	// 처리하고 인접 node들 방문처리하고 enqueue
            if (!visited[w]) {
                visited[w] = true;
                Q.push(w);
            }
        }
    }
}

int main() {
    graph[0] = {1, 2};
    graph[1] = {3};
    graph[2] = {4};

    BFS(0); // 0 1 2 3 4
}

각 탐색법의 특징

• 인접한 node를 하나씩 처리하는 DFS와 달리 BFS는 한 번에 큐에 다 넣으므로 공간복잡도가 더 복잡하다

• BFS는 시작 노드로부터 직접 간선으로 연결된 모든 노드를 먼저 방문하기 때문에 해결책을 찾은 순간 그 해결책이 최단 경로인 것이 보장됨.

• 따라서 미로 찾기같은 최단 경로 문제에서 BFS 사용

unordered_set 해시

• unordered_set<pair<int, int>> visit; 사용하면 에러 발생

• 비정렬 집합은 hash값을 이용하는데 pair<int, int>에 대한 hash 정의가 없어서 에러 발생

해결법 1

• hash 사용 안 하고, set<pair<int, int>> 사용

• pair는 비교연산자<가 이미 정의되어 있어 사용 가능

해결법 2

• 해시 함수 객체를 직접 정의해서 해시를 지원

#include <utility>

struct pair_hash {
    template <class T1, class T2>
    std::size_t operator() (const std::pair<T1, T2>& p) const {
        auto h1 = std::hash<T1>{}(p.first);
        auto h2 = std::hash<T2>{}(p.second);
        return h1 ^ (h2 << 1);  // 해시 조합 예시
    }
};