문제

문제링크 : https://www.acmicpc.net/problem/24445 (단계별로 풀어보기 : 그래프와 순회)

문제 풀이

해당 문제는 24444문제와 인접정점을 방문할 때 순서만 다르다. 다음 링크에 기본적인 풀이법은 적어두었다.
https://velog.io/@jeus/Baekjoon-24444-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%88%98%EC%97%85-%EB%84%88%EB%B9%84-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89-1
해당 문제에서 바뀐점은 내림차순으로 인접정점을 방문하는 것이다. 따라서 간선을 저장한 뒤 인접정점을 내림차순으로 정렬하면 문제는 해결된다. 이 문제도 마찬가지로 배열로 그래프를 만들면 메모리 초과가 날 것이다. 벡터 정렬시 sort()함수를 사용하였고, 디폴트 값은 오름차순 정렬이므로 greater<>() 를 인자로 넣어주어 내림차순으로 정렬되도록 하였다. 다른 방식으로는 compare함수를 구현하여 인자로 넣어주면 된다.(c에서 qsort()함수에서는 이것을 사용한다.)

소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

vector <vector<int>> graph;
vector <int> visited;
int N, M, R, Seq;
queue <int> que;

void input();
void bfs(int n);
void sol();

int main()
{
    fastio;
    input();
    sol();
    return 0;
}

void input()
{
    cin >> N >> M >> R;
    graph.resize(N + 1);
    visited.resize(N + 1);
    int u, v;
    for (int i = 0; i < M; i++) {
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    for (int i = 1; i <= N; i++) sort(graph[i].begin(), graph[i].end(), greater<int>());
}

void bfs(int n)
{
    int u, graphsize;
    visited[n] = ++Seq;
    que.push(n);
    while (que.size() != 0) {
        u = que.front();
        que.pop();
        graphsize = graph[u].size();
        for (int v = 0; v < graphsize; v++) {
            if (visited[graph[u][v]] == 0) {
                visited[graph[u][v]] = ++Seq;
                que.push(graph[u][v]);
            }
        }
    }
}

void sol()
{
    bfs(R);
    for (int i = 1; i < N + 1; i++)    printf("%d\n", visited[i]);
}