99클럽 코테 스터디 10일차 TIL C++ BFS, pair, priority_queue

오늘의 학습 키워드

문제1 : BFS, 단방향 그래프

https://www.acmicpc.net/problem/18352

 

공부한 내용 본인의 언어로 정리하기

문제1 : BFS, 단방향 그래프

 

(1) BFS, 우선순위 큐

이 문제는 최대 레벨(거리)이 정해져 있으므로, 큐에 있는 것들 중에서 레벨이 작은 것부터 꺼내서 작업해야 합니다. 여기서는 deque를 사용하여 큐의 앞에서 노드를 꺼내왔지만, 우선순위를 적용하여 더 낮은 값을 가져올 수도 있습니다. 이를 위해 우선순위 큐(priority queue)를 활용할 수 있습니다. 우선순위 큐를 사용하게 되면, 특정 조건을 만족하는 노드를 보다 효율적으로 처리할 수 있습니다.

• 최대 힙: 기본적으로 priority_queue<int>는 최대 힙을 사용하며, 가장 큰 값이 최상위에 위치합니다.
• 최소 힙: priority_queue\<int, vector\<int>, greater\<int>>와 같이 세 번째 템플릿 인자를 사용하여 최소 힙을 구현할 수 있습니다. 이 경우, 가장 작은 값이 최상위에 위치합니다.
• push()로 요소를 추가하고, pop()으로 가장 높은 우선순위의 요소를 제거합니다. top()으로 최상위 요소를 확인할 수 있습니다.

#include <iostream>
#include <queue> // priority_queue를 사용하기 위한 헤더

using namespace std;

int main() {
    // 정수형 최대 힙으로 구성된 우선순위 큐 생성
    priority_queue<int> maxHeap;

    // 요소 추가
    maxHeap.push(10);
    maxHeap.push(5);
    maxHeap.push(20);
    maxHeap.push(15);

    // 최상위 요소 출력
    cout << "최대값: " << maxHeap.top() << endl; // 20 출력
    maxHeap.pop(); // 20 제거

    cout << "새로운 최대값: " << maxHeap.top() << endl; // 15 출력

    // 최소 힙 사용하기
    priority_queue<int, vector<int>, greater<int>> minHeap; // 최소 힙

    // 요소 추가
    minHeap.push(10);
    minHeap.push(5);
    minHeap.push(20);
    minHeap.push(15);

    // 최상위 요소 출력
    cout << "최소값: " << minHeap.top() << endl; // 5 출력
    maxHeap.pop(); // 5 제거

    return 0;
}

 

(2) pair과 map
pair는 두 개의 값을 하나의 객체로 묶는 데이터 구조로, 주로 관련된 두 값을 함께 사용할 때 유용합니다. map은 키-값 쌍으로 데이터를 저장하는 자료구조입니다. 두 자료형 모두 관련된 데이터를 쌍으로 묶어 관리한다는 공통점이 있습니다. pair는 단순히 두 값을 담는 반면, map은 키를 통해 값을 효과적으로 검색할 수 있는 장점이 있습니다.

• pair: 두 개의 관련된 데이터를 묶어 저장할 때 사용.
• map: 키를 통해 값을 효율적으로 저장하고 조회할 때 사용.

#include <iostream>
#include <utility> // pair를 사용하기 위한 헤더
#include <map>

using namespace std;

int main() {
    pair<int, string> person(1, "Alice"); // ID와 이름을 저장
    cout << "ID: " << person.first << ", Name: " << person.second << endl;

    map<string, int> scores; // 학생 이름과 점수 저장
    scores["Alice"] = 90;
    scores["Bob"] = 85;

    cout << "Alice's score: " << scores["Alice"] << endl; // 점수 조회
    return 0;
}

 

(3) 전체 풀이

#include <iostream>
#include <map>
#include <vector>
#include <deque>

using namespace std;

// 그래프를 표현하는 인접 리스트
map<long long, vector<long long>> graph;
// 방문 여부 및 거리 정보를 저장하는 벡터
vector<long long> visited(300001, -1);

int main() {   
    long long N, M, K, X; // 노드 수, 간선 수, 목표 거리, 시작 노드
    long long A, B; // 간선의 양 끝 노드

    // 입력 받기
    cin >> N >> M >> K >> X;
    while (M-- > 0) {
        cin >> A >> B;
        graph[A].push_back(B); // 단방향 그래프이므로 A -> B 추가
    }

    // BFS 초기화
    deque<pair<long long, long long>> bfsQueue; // (노드, 거리) 쌍을 저장
    bfsQueue.push_back({X, 0}); // 시작 노드와 거리 0으로 초기화

    while (!bfsQueue.empty()) {
        auto currentNode = bfsQueue.front(); // 큐의 앞에서 노드 꺼내기
        bfsQueue.pop_front();

        long long node = currentNode.first; // 현재 노드
        long long level = currentNode.second; // 현재 거리

        // 이미 방문한 노드라면 무시
        if (visited[node] != -1) continue;

        // 현재 노드를 방문 처리
        visited[node] = level;

        // K 거리에 도달한 경우 더 이상 탐색하지 않음
        if (level == K) continue;

        // 인접 노드 탐색
        for (const auto& neighbor : graph[node]) {
            bfsQueue.push_back({neighbor, level + 1}); // 인접 노드를 큐에 추가
        }
    }

    // 결과 출력
    bool found = false; // K 거리의 노드가 발견되었는지 여부
    for (long long i = 1; i <= N; i++) { // 1부터 N까지 탐색
        if (visited[i] == K) {
            found = true; // K 거리의 노드 발견
            cout << i << endl; // 노드 출력
        }
    }

    // K 거리의 노드가 없을 경우
    if (!found) {
        cout << -1 << endl;
    }

    return 0; // 프로그램 종료
}

오늘의 회고

이번 학습을 통해 BFS(너비 우선 탐색) 알고리즘을 사용하여 그래프 탐색을 수행하는 방법을 익혔습니다. 특히, 우선순위 큐의 필요성과 pair, map의 활용에 대해 깊이 이해할 수 있었습니다.