백준 24444 - 알고리즘 수업 - 너비 우선 탐색 1 (C++)

문제 링크입니다. https://www.acmicpc.net/problem/24444

24444번: 알고리즘 수업 - 너비 우선 탐색 1

간단한 BFS 문제였습니다.

일반적인 그래프 문제와 같이 백터를 이용해 양방향 간선을 저장해줍니다.

해당 문제에서는 방문하는 노드는 항상 오름차순이라고 정해졌으니, 백터에 저장된 값들을 전부 정렬해줘야 합니다.

 

정렬을 해준 뒤, 시작점부터 BFS 탐색을 해주면 됩니다. 

이때 방문한 순서를 기억해줘야하니, 변수 하나를 설정해 탐색을 이어나갈 때 마다 하나씩 증가해가며 순서를 저장해줍니다.

 

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdio>

using namespace std;

int N, M, K;
vector<int> connect[100001];
int check[100001];

void bfs(int start){
    int Visit = 1;
    queue<int> q;
    q.push(start);
    check[start] = Visit++;
    while(!q.empty()){
        int x = q.front();
        q.pop();
        for(int i = 0; i < connect[x].size(); i++){
            int xx = connect[x][i];
            if(check[xx] == 0){
                check[xx] = Visit++;
                q.push(xx);
            }
        }
    }
}

void solve(){
    for(int i = 1; i <= N; i++){
        sort(connect[i].begin(), connect[i].end());
    }
    bfs(K);
    for(int i = 1; i <= N; i++){
        cout << check[i] << "\n";
    }
}

int main() {
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M >> K;
    for(int i = 1; i <= M; i++){
        int x, y;
        cin >> x >> y;
        connect[x].push_back(y);
        connect[y].push_back(x);
    }
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글 남겨주세요!