[Baekjoon] 백준 24444 알고리즘 수업 - 너비 우선 탐색 1 - c++

재우·2022년 6월 26일
0

Baekjoon

목록 보기
3/21
post-thumbnail

문제


문제 링크 : https://www.acmicpc.net/problem/24444 (단계별로 풀어보기 : 그래프와 순회)

문제 풀이

해당 문제는 너비 우선 탐색 의사 코드가 나와있다. 따라서 bfs 알고리즘 개념을 공부하고 처음으로 풀어보기 좋은 문제가 될 것 같다.
일단 bfs란 breath frist search, 너비우선탐색으로 시작 정점에서 연결된 정점들을 모두 먼저 방문하고 또 다른 정점에서 연결된 정점들을 모두 방문하는 식의 알고리즘이다. 따라서 구현할 때 queue를 사용하여 시작 정점에서 인접한 정점을 모두 queue에 넣고 방문표시를 남기고 그 다음 queue에서 pop하여 그 정점에서 인접한 정점(방문하지 않은)들을 queue에 넣고 방문표시를 남기고를 queue가 비어있을 때까지 반복하여 탐색하도록 하면 되겠다.
단계별로 풀기 그래프와 순회에서 dfs 문제를 먼저 풀었기 때문에 그 문제에 코드를 변형하여 풀었다. (https://velog.io/@jeus/Baekjoon-24479-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%88%98%EC%97%85-%EA%B9%8A%EC%9D%B4-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89-1) 코드를 구현하면서 헷갈렸던 부분은 벡터 정렬과 벡터를 이용하여 간선을 저장해야한다는 점이었다. 정점의 수와 간선의 수가 크기 때문에 그냥 배열로 구현하였다가는 메모리초과가 날 것이다. 또한 간선을 저장하고 연결된 정점을 오름차순으로 정렬해주어야 한다는 점이 있었다. queue를 사용할 때는 처음에는 직접 구현해보고 익숙해지면 queue 라이브러리를 사용하는 법을 숙지하면 코드 구현에 도움이 된다.

소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

vector <vector<int>> graph;
vector <int> visited;
int N, M, R, Seq;
queue <int> que;

void input();
void bfs(int n);
void sol();

int main()
{   
    fastio;
    input();
    sol();
    return 0;
}

void input()
{
    cin >> N >> M >> R;
    graph.resize(N+1);
    visited.resize(N+1);
    int u,v;
    for(int i=0; i<M; i++){
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    for(int i=1; i<=N; i++) sort(graph[i].begin(), graph[i].end());
}

void bfs(int n)
{
    int u, graphsize;
    visited[n] = ++Seq;
    que.push(n);
    while(que.size()!=0){
        u = que.front();
        que.pop();
        graphsize = graph[u].size();
        for(int v=0; v<graphsize; v++){
            if(visited[graph[u][v]]==0){
                visited[graph[u][v]] = ++Seq;
                que.push(graph[u][v]);
            }
        }
    }
}

void sol()
{
    bfs(R);
    for(int i=1; i<N+1; i++)    printf("%d\n",visited[i]);
}

0개의 댓글