백준 - 24444

문제링크

문제요약

[[백준 - 24479]] 문제와 완전 똑같은 문제이다. 24479 문제는 dfs를 요구했지만 이번문제는 bfs를 요구한다.

bfs(V, E, R) {  # V : 정점 집합, E : 간선 집합, R : 시작 정점
    for each v ∈ V - {R}
        visited[v] <- NO;
    visited[R] <- YES;  # 시작 정점 R을 방문 했다고 표시한다.
    enqueue(Q, R);  # 큐 맨 뒤에 시작 정점 R을 추가한다.
    while (Q ≠ ∅) {
        u <- dequeue(Q);  # 큐 맨 앞쪽의 요소를 삭제한다.
        for each v ∈ E(u)  # E(u) : 정점 u의 인접 정점 집합.(정점 번호를 **오름차순**으로 방문한다)
            if (visited[v] = NO) then {
                visited[v] <- YES;  # 정점 v를 방문 했다고 표시한다.
                enqueue(Q, v);  # 큐 맨 뒤에 정점 v를 추가한다.
            }
    }
}

문제에서는 친절히 bfs의 기본형태를 제공해 준다.

 

따로 문제요약은 작성하지 않겠다. 24479와 완전히 똑같은 입력과 출력을 요구하고 안의 로직만 dfs, bfs 차이가 있으므로 링크로 대체한다.

수도코드

• visited []을 준비한다. 원래는 bool타입의 visited []을 사용하는데 이 문제에서는 방문순서를 저장해야하기때문에 visited[]을 int로 설정해 0이면 방문하지않았음 1이상이면 방문했음을 표시했다.
• bfs를 돌린다.
• visited[]을 출력한다.

---

소스코드는 다음과 같다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int vist[100005] = {0,};
int n, m, r;
vector<int> v[200005];

int main() {
    cin >> n >> m >> r;
    for (int i = 0; i < m; i++) {
        int tmp;
        int tmp1;
        cin >> tmp >> tmp1;
        v[tmp].push_back(tmp1);
        v[tmp1].push_back(tmp);
    }
    for (int i = 0; i < m; i++) {
        sort(v[i].begin(), v[i].end());
    }

    vist[r] = 1;
    queue<int> q;
    q.push(r);
    int cnt = 1;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (int i = 0; i < v[cur].size(); i++) {
            int nxt = v[cur][i];
            if (!vist[nxt]) {
                vist[nxt] = ++cnt;
                q.push(nxt);
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        cout << vist[i] << '\n';
    }
}