백준 32861 (C++) 순열 복원

최초 업로드: 2025-10-30 05:43:13

최근 수정 시간: 2025-10-30 05:43:49

게시자: rlatjwls3333

카테고리: 백준

# [Silver III] 순열 복원

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

## 문제 설명

길이가 $N$인 순열은 $1$부터 $N$까지의 정수가 정확히 한 번씩 등장하는 수열을 의미한다. 예를 들어, $[1]$, $[3,1,4,2,5]$ 등은 순열이지만, $[-1,0,1,3,2]$, $[1,3,5,4]$ 등은 순열이 아니다.

길이가 $N$인 순열 $P$에 대해 비교 행렬을 정의하자. 비교 행렬 $A$는 $N\times N$ 크기이며, 각 원소 $A_{ij}$는 $P_i$와 $P_j$의 상대적 크기에 따라 다음과 같이 정해진다.

비교 행렬 $A$가 주어질 때, 순열 $P$를 복원하는 프로그램을 작성하시오. 만약 비교 행렬이 $A$와 같은 순열이 존재하지 않는다면 <code>-1</code>을 출력한다.

## 입력

첫째 줄에 정수 $N$이 주어진다. $(1\leq N\leq 1\, 000)$

둘째 줄부터 $N$개의 줄에 걸쳐 비교 행렬 $A$가 주어진다. 그중 $i$번째 줄에는 $A$의 $i$번째 행 $A_{i1},A_{i2},\cdots ,A_{iN}$이 공백으로 구분되어 주어진다. 행렬의 모든 원소는 $-1$, $0$, $1$ 중 하나이다.

## 출력

비교 행렬 $A$를 만족하는 순열 $P$가 존재한다면 $P_1,P_2,\cdots ,P_N$을 공백으로 구분하여 차례대로 출력한다. 가능한 순열이 여러 가지라면 아무거나 출력한다.

존재하지 않으면 <code>-1</code>을 출력한다.

## 풀이
i=j면서 A값이 0이 아니거나, i!=j면서 A값이 0인 경우 불가능하다. 나머지 경우는 1이나 -1이 등장한 횟수를 세서, 숫자가 중복되는지 체크하면 된다.

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

bool used[1001];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;

vector<int> res(n);
 for(int i=0;i<n;i++) {
 int cur=n;
 for(int j=0;j<n;j++) {
 int a; cin >> a;
 if(i!=j && !a || i==j && a) {
 cout << -1;
 return 0;
 }
 if(a==1) cur--;
 }
 if(used[cur]) {
 cout << -1;
 return 0;
 }
 used[cur]=true;
 res[i]=cur;
 }
 for(int i=0;i<n;i++) cout << res[i] << ' ';
}
```