백준 28333 - 화이트 칼라 (C++)

문제

• 문제 링크

  
   BOJ 28333 - 화이트 칼라 
  

• 문제 요약

$N$개의 도시와 이들을 잇는 $M$개의 길의 연결 정보가 주어진다.
$1$번 도시에서 $N$번 도시로 이동할 때, 항상 최단 경로로 이동한다고 하자.
거쳐갈 가능성이 있는 모든 도시에 직원을 배치하려 할 때, 어느 도시에 배치해야 하는지 오름차순으로 출력해보자.

• 제한

TL : $1$ sec, ML : $1024$ MB




$2 ≤ N ≤ 1,000$

$1 ≤ M ≤ 50,000$

$1$번 도시에서 $N$번 도시로 이동 가능한 경로는 반드시 하나 이상 존재한다.

알고리즘 분류

• 그래프 이론(graphs)
• 그래프 탐색(graoh_traversal)
• 너비 우선 탐색(bfs)

풀이

$BFS$ 역추적 혹은 그와 비슷한 느낌을 받았다면 문제는 쉬워진다.

모든 간선의 비용이 동일하므로 $BFS$ 진행 시 최단 거리임이 보장된다. 즉, 최초로 방문한 정점에 대해선 그 때의 비용이 반드시 최소 비용이다.

그럼 이용 가능성이 있는지는 어떻게 판단할까?

이 역시 간단하게, 해당 정점에 기록되어 있는 최소 비용과 비교해주면 된다.
최초 방문 시 기록된 비용과 지금 방문하는 데에 들었던 비용이 일치한지 말이다.

이후 이 정보들을 토대로, $N$번 정점으로부터 거꾸로 유망한 후보군들을 따라가며 정답에 추가해주면 되겠다.

※ 유향 그래프임을 유의하자.

전체 코드

#include<bits/stdc++.h>
#define N 1001
using namespace std;
 
vector <int> Gr[N], path[N], dist(N);
int n, m;
 
void Init()
{
    for (int i{}; i < N; i++)
    {
        path[i].clear();
        Gr[i].clear();
        dist[i] = 0;
    }
    cin >> n >> m;
    for (int i, j; m--;)
    {
        cin >> i >> j;
        Gr[i].push_back(j);
    }
}
void BFS()
{
    queue <int> Q;
    for (Q.push(dist[1] = 1); Q.size();)
    {
        int now(Q.front()); Q.pop();
 
        for (int& next : Gr[now])
        {
            int cost(dist[now] + 1);
            if (!dist[next])
            {
                path[next].push_back(now);
                dist[next] = cost;
                Q.push(next);
            }
            else if (cost == dist[next])
                path[next].push_back(now);
        }
    }
}
void End()
{
    set <int> ans{ n };
 
    bitset <N> visit;
    visit[n] = 1;
 
    queue <int> Q;
    for (Q.push(n); Q.size();)
    {
        int now(Q.front()); Q.pop();
 
        for (int& next : path[now])
            if (!visit[next])
            {
                ans.insert(next);
                visit[next] = 1;
                Q.push(next);
            }
    }
    for (auto& i : ans) cout << i << ' ';
    cout << '\n';
}
int main()
{
    int t; cin >> t;
    while (t--)
    {
        Init();
        BFS();
        End();
    }
}

comment

끝