백준 33706 (C++) 오름차순 최단 경로

최초 업로드: 2025-04-14 11:38:05

최근 수정 시간: 2025-07-25 09:56:05

게시자: rlatjwls3333

카테고리: 백준

# [Gold IV] 오름차순 최단 경로

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

## 문제 설명

정점 $N$개와 간선 $M$개로 이루어진 방향 없는 그래프가 주어진다. 이 그래프의 간선의 비용은 아직 정해지지 않았다. 아래의 조건을 만족하도록 그래프의 간선의 비용을 정할 수 있는지 판별해 보자.

<ul>
	<li>간선의 비용은 양의 정수여야 한다.</li>
	<li>모든 $\left(i, j\right)$쌍에 대해서 $\left(1 \lt i \lt j\leq N\right)$, 정점 $1$에서 정점 $i$로의 최단 경로의 비용이 정점 $1$에서 정점 $j$로의 최단 경로의 비용보다 작아야 한다.</li>
</ul>

최단 경로의 구체적인 정의는 아래 힌트에 나와 있다.

## 입력

첫째 줄에 정점의 개수 $N$과 간선의 개수 $M$이 공백으로 구분되어 주어진다. $(2\leq N\leq 200\, 000;$ $1\leq M\leq 200\, 000)$

이어지는 $M$개의 줄에 정수 $a$와 $b$가 공백으로 구분되어 주어진다. 이는 정점 $a$와 정점 $b$를 연결하는 간선이 존재함을 의미한다. $\left(1\leq a \lt b\leq N\right)$

주어진 그래프의 모든 정점이 연결되어 있고, 중복된 간선이 주어지지 않음이 보장된다.

## 출력

주어진 조건을 만족하도록 그래프의 간선의 비용을 정해줄 수 있다면 <code>YES</code>를, 그렇지 않다면 <code>NO</code>를 출력한다.

## 풀이
#### 간선의 가중치는 임의로 정할 수 있습니다. 따라서 어떤 가중치를 설정하든 불가능한 경우를 찾으면 됩니다. 어떠한 경우에서든 불가능한 경우는 1에서 임의의 한 정점에 도달하기 위해 그것보다 큰 정점을 반드시 지나야하는 경우입니다.

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

const int MAX = 200000;

int n, m;
int visited[MAX];
vector<vector<int>> conn(MAX);

string bfs() {
 visited[0]=true;
 queue<int> q; q.push(0);
 while(!q.empty()) {
 int cur = q.front(); q.pop();
 for(int next:conn[cur]) {
 if(!visited[next]) {
 visited[next]=true;
 q.push(next);
 }
 }
 }
 
 for(int i=0;i<n;i++) {
 if(!visited[i]) {
 return "NO";
 }
 }
 return "YES";
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 cin >> n >> m;
 while(m--) {
 int a, b; cin >> a >> b;
 conn[min(a, b)-1].push_back(max(a, b)-1);
 }
 cout << bfs();
}
```