백준 24444_알고리즘 수업 - 너비 우선 탐색 1 문제풀이 in C++
문제 URL
https://www.acmicpc.net/problem/24444
문제 요구사항
- N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다.
- 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다.
- 인접 정점은 오름차순으로 방문한다.
- 정점 R에서 시작하여 깊이 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자.
- 첫째 줄부터 N개의 줄에 정수를 한 개씩 출력한다.
- i번째 줄에는 정점 i의 방문 순서를 출력한다.
- 시작 정점의 방문 순서는 1이다.
- 시작 정점에서 방문할 수 없는 경우 0을 출력한다.
- 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다.
- 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방향 간선을 나타낸다.
접근 방법
- 문제에서 착하게 의사 코드를 제시 해주고 있다. 문제에서 주어진 의사 코드를 구현하면 된다. 나는 BFS의 기본 개념을 까먹은 거 같아 해당 문제를 풀어봤다.
풀이 순서
- N(정점의 개수), M(간선의 개수), R(시작 정점)을 입력 받는다.
- 이후, M(간선의 개수)만큼 반복하여 간선 정보를 입력 받는다.
- 나는 간선 정보를 vector<vector
>로 해서 받았다. - 해당 간선 정보의 각 인덱스를 오름차순으로 정렬한다.
- BFS 수행
- 이때, 매개변수로 받게 되는 정점은 check 하여, 중복으로 올 수 없게 한다.
- queue
변수를 생성하여, 해당 큐에 매개변수로 받은 시작점을 넣는다. - queue가 empty일 때까지 while문을 반복한다.
- queue의 맨 앞 원소를 추출한다. -> 목적지 인덱스가 됨
- result의 해당 목적지 인덱스에 cnt값을 넣고, cnt+=1 한다.
- queue에 해당 목적지를 pop()한다.
- v벡터의 목적지 인덱스 size만큼 for문을 반복한다.
- v[목적지 인덱스][i] 값을 nx로 지정하고, check[nx]가 false면 check[nx]를 true로 설정하고 queue에 nx 값을 넣는다.
- 이와 같은 작업 반복
- 1부터 N(정점의 개수)만큼 result의 각 value 출력
소스코드
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
int N, M, R;
vector<vector<int>> v(100001, vector<int>());
vector<int> result(100001, 0);
bool check[100001];
void input() {
cin >> N >> M >> R;
memset(check, false, sizeof(check));
for (int i = 0; i < M; i++) {
int a, b;
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
}
void sortingAsc() {
for (int i = 1; i <= N; i++) {
sort(v[i].begin(), v[i].end());
}
}
void BFS(int startX) {
check[startX] = true;
queue<int> q;
q.push(startX);
int cnt = 1;
while (!q.empty()) {
int xx = q.front();
result[xx] = cnt;
cnt++;
q.pop();
for (int i = 0; i < v[xx].size(); i++) {
int nx = v[xx][i];
if (check[nx] == false) {
check[nx] = true;
q.push(nx);
}
}
}
}
void output() {
for (int i = 1; i <= N; i++) {
cout << result[i] << "\n";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
input();
sortingAsc();
BFS(R);
output();
return 0;
}