[Algorithm] C++ 백준 5920번: Cow Photography

문제의 본질은 다섯 장의 사진에서 관찰한 상대적 순서 정보만 가지고 원래 순열을 복원하는 정렬·구현 문제입니다.
각 소 쌍에 대해 다섯 번 중 최소 세 번 이상 등장하는 상대적 순서가 곧 원래 줄 서기에서의 순서라는 사실을 이용해, 정렬 비교 함수를 설계하는 것이 핵심입니다.

문제 정보

문제 링크: https://www.acmicpc.net/problem/5920

문제 요약:
농부 존은 \(1 \le N \le 20\,000\) 마리의 소를 1부터 \(N\)까지 번호 매겨 한 줄로 세우고 사진을 찍으려 한다.
원래 의도한 순서를 \(A[1..N]\)라 할 때, 사진을 찍기 직전에 최대 한 마리의 소가 자신의 위치를 비워 다른 위치로 이동하는 과정이 일어나며, 이런 일이 총 5장의 사진에 대해 반복된다.
각 사진은 시작 순서 \(A\)에서 최대 한 마리의 소만 다른 위치로 옮겨진 결과이며, 한 소는 여러 사진에서 직접 움직이지 않는다(직접 움직이는 사진은 많아야 한 번).
이 다섯 장의 사진에 찍힌 줄 서기 결과가 주어질 때, 원래 의도한 순서 \(A\) 를 복원하는 것이 목표이다.

입력 형식:

• 첫 줄에 소의 수 \(N\)이 주어진다.
• 이후 5장 × \(N\)줄에 걸쳐, 각 사진마다 줄 서 있는 순서대로 \(N\)마리의 소 번호가 한 줄에 하나씩 주어진다.

출력 형식:

• 1줄에 한 소씩, 원래 의도된 순서 \(A[1..N]\) 를 출력한다.

제한 조건:

• \(1 \le N \le 20\,000\)
• 소 번호는 항상 1부터 \(N\)까지이며, 각 사진은 하나의 순열이다.
• 시간 제한: 1초
• 메모리 제한: 128MB

입출력 예제

입력 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

5
1
2
3
4
5
2
1
3
4
5
3
1
2
4
5
4
1
2
3
5
5
1
2
3
4

출력 1:

1
2
3
4
5

1
2
3
4
5

설명(요약):
각 사진에서 서로 다른 한 마리의 소가 맨 앞으로 이동했지만, 모든 소 쌍의 상대적 순서를 다섯 번 비교해 보면 결국 원래 순열 \(1,2,3,4,5\)가 일관되게 드러난다.

접근 방식

핵심 관찰

• 한 쌍의 소 \((x, y)\)에 대해, 원래 순서에서 \(x\)가 \(y\)보다 앞에 있다고 가정하자.
  • 어떤 사진에서는 아무도 움직이지 않거나, 둘이 아닌 다른 소가 움직인다면 \(x\)와 \(y\)의 상대적 순서는 그대로 유지된다.
  • 상대적 순서가 뒤집힐 수 있는 경우는 사진에서 이동하는 소가 \(x\)이거나 \(y\) 일 때뿐이다.
• 각 소는 최대 한 사진에서만 직접 이동하므로, 쌍 \((x, y)\)가 상대 순서를 잃을 수 있는 사진은 최대 2장이다.
• 사진은 총 5장이므로,
  \[ \text{원래 } x < y \Rightarrow \text{5장 중 최소 3장 이상에서 } x \text{가 } y \text{보다 앞에 선다.} \] 가 항상 성립한다.
• 따라서 다섯 장의 사진에서 “더 자주 앞에 나오는 쪽”이 원래 순열에서도 앞에 온다는 기준으로 비교 함수를 만들면:
  • 모든 소 쌍에 대해 비교 결과가 반드시 원래 순열과 일치하고,
  • 이 비교 함수는 일관된 전순서(Transitive Order) 를 이루므로 일반적인 sort를 그대로 사용할 수 있다.

결국, 소 번호를 1부터 \(N\)까지 준비한 뒤,
각 소 쌍 \((a, b)\)에 대해 5개 사진 중 \(a\)가 더 앞에 있는 사진이 3번 이상이면 \(a < b\) 로 간주하는 정렬 비교 함수로 정렬하면 된다.

알고리즘 설계 (Mermaid Flowchart)

flowchart TD
    A[시작: N 입력] --> B[5개의 사진에서
각 소의 위치 pos[k][id] 저장]
    B --> C[소 번호 배열 cows = 1..N 초기화]
    C --> D[정렬 비교 함수 정의]
    D --> E[정렬: sort(cows.begin, cows.end, cmp)]
    E --> F[정렬된 cows를 한 줄에 하나씩 출력]

    D --> D1[cmp(a, b):
각 사진 k=0..4에 대해
pos[k][a] < pos[k][b] 인 횟수 count]
    D1 --> D2[만약 count >= 3 이면
a가 b보다 앞선다고 판단]

단계별 로직

1. 입력 파싱 및 위치 배열 구성

   • 사진은 총 5장이며, 각 사진마다 \(N\)줄씩 소 번호가 주어진다.
   • pos[k][id]를 k번째 사진에서 소 id가 선 위치(0-based 인덱스) 로 저장한다.
   • 이로써 임의의 두 소 a, b에 대해, 다섯 사진에서의 상대적 위치를 \(O(1)\)에 비교할 수 있다.

2. 소 번호 배열 초기화

   • cows = {1, 2, ..., N} 으로 순열을 하나 만들어, 이후 이 배열을 정렬하여 정답 순열을 얻는다.

3. 비교 함수 정의

   • 두 소 a, b를 비교할 때:
     • cnt = 0으로 초기화한 뒤, 다섯 사진 k = 0..4에 대해
       • if (pos[k][a] < pos[k][b]) cnt++; 를 수행한다.
     • 다섯 장 중 3장 이상에서 a가 b보다 앞이라면 a가 원래 순서에서도 앞에 있으므로 cmp(a, b) = true로 반환한다.
   • 이 규칙에 의해, 모든 소 쌍에 대해 원래 순서와 동일한 비교 결과를 얻을 수 있다.

4. 정렬 수행

   • 위 비교 함수를 이용해 sort(cows.begin(), cows.end(), cmp)를 호출하면,
     • 정렬 결과는 곧 원래 의도된 순서 \(A[1..N]\) 가 된다.

5. 결과 출력

   • 정렬된 cows 배열의 원소를 한 줄에 하나씩 그대로 출력하면 된다.

복잡도 분석

구현 코드

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

// 42jerrykim.github.io에서 더 많은 정보를 확인 할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    if (!(cin >> N)) return 0;

    const int K = 5;
    vector<vector<int>> pos(K, vector<int>(N + 1));

    // 각 사진에서의 위치 기록
    for (int k = 0; k < K; ++k) {
        for (int i = 0; i < N; ++i) {
            int id;
            cin >> id;
            pos[k][id] = i;  // 0-based index
        }
    }

    vector<int> cows(N);
    iota(cows.begin(), cows.end(), 1);  // 1..N

    auto cmp = [&](int a, int b) {
        if (a == b) return false;
        int cnt = 0;
        for (int k = 0; k < K; ++k) {
            if (pos[k][a] < pos[k][b]) ++cnt;
        }
        // 최소 3장의 사진에서 앞선 쪽이 원래 순서에서도 앞선다
        return cnt >= 3;
    };

    sort(cows.begin(), cows.end(), cmp);

    for (int id : cows) {
        cout << id << '\n';
    }

    return 0;
}

코너 케이스 및 실수 포인트

참고 문헌 및 출처

• 백준 5920번: Cow Photography
• USACO December 2011 Contest Bronze – Cow Photography