백준 24445_알고리즘 수업 - 너비 우선 탐색 2 문제풀이 in C++

2022년 05월 26일 in Devlog on Algorithm

1. 문제 URL
2. 문제 요구사항
3. 접근 방법
4. 풀이 순서
5. 소스코드
6. 문제 풀이 결과

문제 URL

---

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

문제 요구사항

---

• 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인 양방향 간선을 나타낸다.

접근 방법

---

• 문제에서 착하게 의사 코드를 제시 해주고 있다. 문제에서 주어진 의사 코드를 구현하면 된다.
• 내림차순의 경우 라이브러리의 sort 함수에서 greater<>()인자를 줘 내림차순 정렬하면 된다.
• 나는 BFS의 기본 개념을 까먹은 거 같아 해당 문제를 풀어봤다.

풀이 순서

---

1. N(정점의 개수), M(간선의 개수), R(시작 정점)을 입력 받는다.
2. 이후, M(간선의 개수)만큼 반복하여 간선 정보를 입력 받는다.
3. 나는 간선 정보를 vector<vector>로 해서 받았다.
4. 해당 간선 정보의 각 인덱스를 내림차순으로 정렬한다.
5. 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 값을 넣는다.
   • 이와 같은 작업 반복
6. 1부터 N(정점의 개수)만큼 result의 각 value 출력

소스코드

---

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>

using namespace std;

int N, M, R;
vector<vector<int>> v(100001,vector<int>());
bool check[100001];
vector<int>result(100001, 0);
int cnt = 1;
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 sortingDesc() {
	for (int i = 1; i <= N; i++) {
		sort(v[i].begin(), v[i].end(), greater<>());
	}
}

void BFS(int startX) {
	check[startX] = true;

	queue<int> q;

	q.push(startX);

	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();
	sortingDesc();
	BFS(R);
	output();

	return 0;
}

문제 풀이 결과

---