백준 34139 (C++) 의식의 광장

최초 업로드: 2025-08-19 01:35:04

최근 수정 시간: 2025-08-19 01:35:28

게시자: rlatjwls3333

카테고리: 백준

# [Silver II] 의식의 광장

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

## 문제 설명

도시가 완성된 뒤, 사람들은 그 빛을 기념하기 위한 의식을 열었다. 마을의 광장에는 작은 빛의 점들이 놓였고, 각각은 고유한 빛을 머금은 채 조용히 빛났다.

이제, 의식의 다음 단계가 시작된다. 각 빛은 정해진 방향으로 흘러가며, 새로운 자리를 비추기 시작한다. 빛은 그 이동 경로를 따라 퍼지며, 그 길이와 흐름은 서로 겹치지 않도록 조율되어야 한다.

그들이 정리한 빛의 방향과 흐름을 되짚고, 빛이 퍼져나가는 장면을 다시 완성해 보아라.

<hr>
광장의 바닥은 격자로 이루어져 있으며, 위아래로는 총 $H$행이며 좌우로는 충분히 넓다. 위에서부터 $r$번째 행, 왼쪽에서부터 $c$번째 열의 칸을 $(r,c)$로 표기한다.

사람들은 이곳에 $N$개의 빛을 배치했다. 의식의 흐름에 따라, 각 빛은 오른쪽 방향(열 번호가 증가하는 방향)으로 일정 거리만큼 이동해야 한다.

빛의 움직임을 구현하는 것은 어려운 일이기 때문에, 몇 가지 제약 조건이 있다.

<ul>
	<li>각 빛은 $1\times 1$ 크기의 정사각형 판의 중심에 고정되어 있다.</li>
	<li>$N$개의 빛이 놓인 판은 각각 $1$ 이상 $N$ 이하의 서로 다른 정수 거리만큼 이동해야 한다.</li>
	<li>$N$개의 판은 동시에 이동을 시작하고, 동시에 도착하며, 이동 중에는 일정한 속도를 유지해야 한다.</li>
	<li>이동 중 두 판이 겹쳐서는 안 된다. 단, 경계가 닿는 것은 괜찮다.</li>
	<li>이동이 끝난 후, 모든 빛은 서로 다른 열에 위치해야 한다.</li>
</ul>

예를 들어, $H=2$, $N=4$이고, 빛의 시작 위치가 각각 $(1,1) ,(1,3) ,(2,2) ,(2,3)$인 경우를 생각해 보자. 아래 그림에서 각 빛 판의 위치는 서로 다른 색의 정사각형으로 표시되어 있다.

이때 다음과 같은 방식으로 이동 거리를 배정하면 모든 조건을 만족하게 된다.

아래는 빛의 이동 과정을 시간 순서대로 나타낸 그림이다. 각 그림은 이동이 시작된 시점, 이동 중간의 시점, 이동이 끝난 시점의 빛의 위치를 나타낸다.

빛의 흐름이 겹치지 않도록 이동 거리를 배정할 수 있는지 판단하고, 가능하다면 그 방법을 구하라.

## 입력

첫 줄에 두 정수 $H$와 $N$이 공백으로 구분되어 주어진다.

이후 $N$개의 줄에 걸쳐, 각 빛의 시작 위치를 나타내는 두 정수 $r_i$, $c_i$가 공백으로 구분되어 주어진다. 이는 $i$번째 빛의 시작 위치가 $(r_i,c_i)$라는 뜻이다.

## 출력

만약 조건을 만족하도록 빛의 이동 거리를 배정할 수 있다면, 첫째 줄에 <code>YES</code>를 출력한다.

둘째 줄에는 $N$개의 정수 $B_1,B_2,\cdots ,B_N$을 공백으로 구분해 출력한다. 이는 $i$번째 빛이 오른쪽으로 $B_i$만큼 움직여야 한다는 의미이다. 가능한 방법이 여러 가지라면 그중 아무것이나 출력해도 좋다.

만약 조건을 만족하도록 빛의 이동 거리를 배정할 수 없다면, 첫째 줄에 <code>NO</code>를 출력한다.

## 풀이
#### 속도가 거리에 비례하기에 정렬해서 왼쪽부터 작은 거리를 할당해주었다.

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

struct light {
 int r, c, idx;
 bool operator<(const light l) const {
 return c < l.c;
 }
};

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int h, n; cin >> h >> n;
 vector<light> v(n);
 for(int i=0;i<n;i++) {
 cin >> v[i].r >> v[i].c;
 v[i].idx = i;
 }
 sort(v.begin(), v.end());

vector<int> res(n);
 for(int i=0;i<n;i++) res[v[i].idx]=i+1;

cout << "YES\n";
 for(int e : res) cout << e << ' ';
}
```