[백준 24446] 알고리즘 수업 - 너비 우선 탐색 3

문제

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

24446번: 알고리즘 수업 - 너비 우선 탐색 3

 

 

문제 분석

무방향 그래프를 만들고  시작 정점부터 BFS를 돌려준다. 

 

시작 정점을 0으로 다음으로 방문하는 노드는 1, 그다음은 2이렇게 1식 올라간 것을 출력한다. 여기서 방문하지 않은 노드는 -1로 표시한다. 

 

 

알고리즘 설계

정점의 수, 간선의 수, 시작 정점을 입력 받는다. 

 

어떤 노드끼리 연결되어 있는지 확인하기 위하여 이중vector graph를 만들고, 몇 번쨰에 방문했는지 알려줄 visited라는 vector을 하나 만들고, 각각 초기화 시켜준다. visited는 -1로 초기화 해준다. 

 

이후 BFS를 돌려 연결 되어 있으며 방문하지 않은 노드라면 그 노드로 BFS를 돌려준다. 

 

 

유의점

BFS를 이해하지 못 하였다면 어려울 수 있기에 충분히 이해된 상태에서 문제 푸는 것을 권장한다.

 

 

코드

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

void BFS(int index);

vector<vector<int>> graph;
vector<int> visited;
int n, m, v;

int main()
{
    int input1, input2;
    cin >> n >> m >> v;

    graph.resize(n + 1);
    visited = vector<int>(n + 1, -1);

    while (m--)
    {
        cin >> input1 >> input2;
        graph[input1].push_back(input2);
        graph[input2].push_back(input1);
    }

    for (int i = 1; i < graph.size(); ++i)
        sort(graph[i].begin(), graph[i].end());

    BFS(v);

    for (int i = 1; i < visited.size(); ++i)
        cout << visited[i] << '\n';
}

void BFS(int index)
{
    queue<int> que;
    que.push(index);
    visited[index] = 0;

    while (!que.empty())
    {
        int current = que.front();
        que.pop();

        for (int i : graph[current])
        {
            if (visited[i] != -1)
                continue;
            visited[i] = visited[current] + 1;
            que.push(i);
        }
    }
}