백준/24445/BFS/알고리즘 수업 - 너비 우선 탐색2

링크텍스트

문제 해석

너비 우선 탐색을 하는데 이 때 서로 인접한 정점을 방문 할 때는 내림차순으로 방문하는 문제입니다.

문제 풀이

BFS를 하기전에 인접한 점들을 저장한 배열을 내림차순으로 정렬하면 되는 문제입니다.
저는 반대로 오름차순으로 정렬 후 끝에 배열부터 방문하였습니다.

풀이

첫번째 풀이

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

vector<int>map[100'000];
int visited[100'001];

queue<int>q;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int N, M, R = 0;
	cin >> N >> M >> R;

	for (int i = 0;i < M;i++)
	{
		int u, v = 0;
		cin >> u >> v;
		map[u].push_back(v);
		map[v].push_back(u);
	}

	for (int i = 1;i <= N;i++)
	{
		::sort(map[i].begin(), map[i].end());
	}
	
	q.push(R);
	int visited_count = 1;
	visited[R] = visited_count++;
	while (!q.empty())
	{
		int cur = q.front(); q.pop();
		for (int i = map[cur].size() - 1;i >= 0;i--)
		{
			int nxt = map[cur][i];
			if (visited[nxt] != 0)continue;
			q.push(nxt);
			visited[nxt] = visited_count++;
		}
	}

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

	return 0;
}