[백준 24446번] 알고리즘 수업 - 너비 우선 탐색 3 (C++)

문제링크 : https://www.acmicpc.net/problem/24446

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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, M, R;
vector<int>v[100001];
int visited[100001];

void bfs()
{
    memset(visited, -1, sizeof(visited));
    queue<int>q;
    q.push(R);
    visited[R]=0; //시작점

    while(!q.empty())
    {
        int cur = q.front();
        q.pop();
        for(int i=0; i<v[cur].size(); i++)
        {
            int next = v[cur][i];
            if(visited[next]!=-1) continue; //방문불가한 경우 스킵
            visited[next] = visited[cur]+1; //깊이 증가
            q.push(next);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N >> M >> R;
    for(int i=1; i<=M; i++)
    {
        int x, y;
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }

    bfs();
    for(int i=1; i<=N; i++) cout << visited[i] << "\n";
    return 0;
}

 

간단한 bfs 문제에 깊이를 저장하는 것을 추가한 문제이다.

시작점은 깊이가 0이기에 0으로 시작하고 다음값에 대해 방문이 불가능한 -1이 아니라면 현재 깊이에 +1를 하여 저장해준다.

이를 모든 값에 대해 반복해주고 깊이를 담은 배열을 따로 출력해준다.

 

방문이 불가하다는 -1을 표시하기 위해 깊이를 담을 배열을 -1로 초기화 해주고 시작한다.