99클럽 코테 스터디 8일차 TIL C++ BFS(최단경로), Deque

오늘의 학습 키워드

문제1 : BFS(최단경로), Deque

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

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

문제1 : BFS(최단경로), Deque

 

(1) bfs로 최단 경로 찾기

BFS(너비 우선 탐색)는 그래프의 모든 정점을 레벨별로 탐색하는 알고리즘입니다. 이 알고리즘은 시작 노드로부터 가까운 노드부터 차례로 탐색해 나가며, 주로 최단 경로 문제를 해결하는 데 사용됩니다. BFS는 큐를 사용하여 구현됩니다. 큐는 FIFO(First In First Out) 방식으로 동작하여, 가장 먼저 들어간 노드가 가장 먼저 처리됩니다. 이를 통해 최단 경로를 보장할 수 있습니다.

 

(2) Deque

deque는 "double-ended queue"의 약자로, 양쪽 끝에서 삽입과 삭제가 가능한 자료구조입니다. C++의 STL에서 제공하는 deque는 BFS 구현 시 유용하게 사용할 수 있습니다. 일반적인 큐와 비슷하지만, deque는 양쪽 끝에서 데이터를 추가하고 제거할 수 있는 점이 특징입니다.

 

DEQUE의 간단한 사용법:

• push_back(value): 큐의 뒤쪽에 요소 추가
• push_front(value): 큐의 앞쪽에 요소 추가
• pop_back(): 큐의 뒤쪽 요소 제거
• pop_front(): 큐의 앞쪽 요소 제거
• front(): 큐의 앞쪽 요소 접근

(3) main 함수는 0을 리턴해야 합니다.

C++ 프로그램의 main 함수는 정수 값을 반환해야 하며, 일반적으로 성공적으로 종료되었음을 나타내기 위해 0을 반환합니다. 그렇지 않은 경우, 아래와 같은 문제를 만날 수 있습니다.

 

(4) 전체 풀이 

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

using namespace std;

map<int, vector<int>> m_graph;

int main() {   
    int N, m, a, b, x, y;
    cin >> N; // 노드 수
    cin >> a >> b; // 시작 노드 a와 목표 노드 b
    cin >> m; // 엣지 수

    // 그래프 초기화
    while (m-- > 0) {
        cin >> x >> y;
        m_graph[x].push_back(y);
        m_graph[y].push_back(x);
    }

    // BFS 초기화
    deque<vector<int>> queue; // BFS를 위한 큐
    vector<int> visited(101, -1); // 방문 배열 초기화 (-1로 설정)
    queue.push_back({a, 1}); // 시작 노드와 카운트 초기화

    while (!queue.empty()) {
        vector<int> current = queue.front();
        queue.pop_front(); // 큐에서 제거
        int n = current[0]; // 현재 노드
        int cnt = current[1]; // 현재 카운트

        if (n == b) { // 목표 노드에 도달한 경우
            cout << cnt - 1 << endl; // 카운트 반환
            return 0; // 프로그램 종료
        }

        // 현재 노드 방문 처리
        if (visited[n] != -1) continue; // 이미 방문한 경우 건너뛰기
        visited[n] = cnt; // 방문 기록

        // 다음 노드 탐색
        vector<int> vecNxt = m_graph[n];
        for (int i = 0; i < vecNxt.size(); i++) {
            int nxt = vecNxt[i]; // 다음 노드
            if (visited[nxt] == -1) { // 방문하지 않은 노드인 경우
                queue.push_back({nxt, cnt + 1}); // 다음 노드와 카운트 증가
            }
        }
    }

    cout << -1 << endl; // 목표 노드에 도달할 수 없는 경우
    return 0; // 프로그램 종료
}

오늘의 회고

오늘은 BFS와 deque를 활용하여 그래프 탐색 문제를 해결하는 방법을 배웠습니다. BFS를 통해 최단 경로를 찾는 과정에서, 어떻게 큐를 사용하여 노드를 탐색하는지 이해할 수 있었습니다.