백준 3526 (C++) 이상적인 경로

최초 업로드: 2025-07-28 00:42:41

최근 수정 시간: 2025-07-28 00:42:41

게시자: rlatjwls3333

카테고리: 백준

# [Platinum V] 이상적인 경로

[문제 링크](https://www.acmicpc.net/problem/3526)

## 문제 설명

라인 제로 놀이 동산에 새로운 미로가 생겼다. 미로는 방 n개와 방을 연결하는 통로 m개로 이루어져 있다. 통로는 ci 색으로 색칠되어져 있다. 미로는 입구는 1번 방이고, 출구는 n번 방이다. 미로에 들어가려면 헬리콥터를 타고 1번 방으로 낙하해야 한다.

미로를 만든 선영이는 다음날 미로 탈출 대회를 개최하려고 한다. 참가자는 1번 방 에서 출발하고, n번 방에 도착할 때까지 지난 복도의 색상을 모두 종이에 적는다. 대회를 우승하려면 종이에 적은 숫자의 개수가 적어야 한다. 또, 종이에 적은 숫자의 개수가 같은 경우에는 가장 이상적인 경로인 사람이 우승하게 된다. 다른 경로보다 모두 사전 순으로 앞서는 경로를 이상적인 경로라고 한다.

미로의 정보가 주어졌을 때, 1번 방에서 n번 방으로 가는 가장 이상적인 경로를 구하는 프로그램을 작성하시오.

## 입력

첫째 줄에 방의 수 n과 복도의 수 m이 주어진다. (2 ≤ n ≤ 100,000, 1 ≤ m ≤ 200,000) 다음 m개 줄에는 복도의 정보가 주어지며, 정보는 세 정수 ai, bi, ci로 이루어져 있다. ai와 bi는 복도가 연결하는 방의 번호이고, ci는 복도의 색상이다. (1 ≤ ai, bi ≤ n, 1 ≤ ci ≤ 109) 복도는 양방향이며, 두 방을 연결하는 복도의 개수는 1개보다 많을 수도 있다. 또, 자기 자신으로 되돌아오는 복도가 존재할 수도 있다. 항상 1번 방에서 n번 방으로 갈 수 있는 미로만 입력으로 주어진다.

## 출력

첫째 줄에 1번 방에서 n번 방으로 가는 최단 경로의 길이를 출력한다. 둘째 줄에는 가장 이상적인 경로의 색을 지나가는 순서대로 출력한다.

## 풀이
#### n부터 시작하여 1까지 오는 최단 경로를 찾아주고, 1에서 그 최단 경로 중 c가 가장 작은 길만 따라 갔습니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

const int MAX = 100'001;

int n, m;
int depth[MAX];

struct element {
 int e, c;
 bool operator<(const element e) const {
 return c < e.c;
 }
};

vector<vector<element>> conn(MAX);

void bfs() {
 depth[n]=1;
 queue<int> q; q.push(n);
 while(!q.empty()) {
 int cur = q.front(); q.pop();
 for(auto next:conn[cur]) {
 if(!depth[next.e]) {
 q.push(next.e);
 depth[next.e] = depth[cur]+1;
 }
 }
 }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    while(m--) {
        int a, b, c; cin >> a >> b >> c;
        conn[a].push_back({b, c});
        conn[b].push_back({a, c});
    }
    bfs(); // 최단경로를 찾기 위한 역방향 bfs

vector<int> res;
 queue<int> q; q.push(1);
 while(!q.empty()) {
 if(q.front()==n) break;

// 모든 다음 깊이의 후보 탐색
 vector<element> nextCandidates;
 while(!q.empty()) {
 int cur = q.front(); q.pop();
 for(auto next:conn[cur]) {
 if(depth[next.e]==depth[cur]-1) {
 nextCandidates.push_back(next);
 }
 }
 }
 sort(nextCandidates.begin(), nextCandidates.end());

// c가 가장 작은 다음 깊이의 후보만 남기기
 int minC = (*nextCandidates.begin()).c;
 vector<bool> visited(n+1);
 for(auto e : nextCandidates) {
 if(minC == e.c && !visited[e.e]) {
 q.push(e.e);
 visited[e.e]=true;
 }
 }
 res.push_back(minC);
 }

cout << res.size() << '\n';
 for(int e : res) cout << e << ' ';
}
```