Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 구하는 seq[i] = i의 최대 개수: 순열 교환 연산 문제 풀이

문제 개요

정수로 이루어진 순열 seq와, 0부터 n-1 범위의 정수 쌍 m개로 구성된 배열 pairs가 주어집니다. 우리는 seq[i] = i(0 ≤ i < n)를 만족하는 i의 개수를 최대화하기 위해 다음 연산을 원하는 만큼 반복해서 수행할 수 있습니다.

  • 0 ≤ j < m인 정수 j를 하나 선택한 뒤, seq[pairs[j]의 첫 번째 값]과 seq[pairs[j]의 두 번째 값]의 위치를 서로 맞바꿉니다.

목표는 연산을 여러 번 수행한 결과 seq[i] = i가 성립하는 i의 최대 개수를 구하는 것입니다.

예를 들어 n = 4, m = 2, seq = {0, 3, 2, 1}, pairs = {{0, 1}, {2, 3}}이 입력으로 주어지면 출력은 2가 됩니다.

접근 방법

이 문제의 핵심은 그래프의 연결 요소(Connected Component) 개념입니다. pairs에 등장하는 두 인덱스를 서로 연결된 노드로 생각하면, 같은 연결 요소에 속한 위치들끼리는 몇 번이든 자유롭게 값을 교환할 수 있습니다. 따라서 어떤 값 v가 위치 j와 동일한 연결 요소에 속해 있다면, 적절한 교환을 통해 seq[j] = v로 만드는 것이 항상 가능합니다.

이를 바탕으로 한 해결 절차는 다음과 같습니다.

  1. 먼저 이미 seq[i] = i를 만족하는 위치의 개수를 셉니다.
  2. pairs 정보를 인접 리스트 형태로 변환합니다.
  3. DFS를 수행하여 각 연결 요소에 고유 번호를 부여하고, 같은 연결 요소에 속한 인덱스들을 모읍니다.
  4. 각 연결 요소마다, 해당 요소에 속한 위치 j 중에서 값 seq[j] 역시 같은 연결 요소에 속하면서 아직 제자리에 있지 않은(seq[j] ≠ j) 경우의 개수를 정답에 더합니다.

순열의 특성상 하나의 값이 두 위치에 동시에 존재할 수 없으므로, 위 과정에서 중복 계산은 발생하지 않습니다. 전체 시간 복잡도는 O(n + m)으로 매우 효율적입니다.

의사 코드

N := 100
크기 N의 배열 tp 선언
크기 N의 배열 vtmp, vis 선언

dfs(j, k) 함수:
    tp[j] := k
    vtmp[k]의 끝에 j 삽입
    vis[j]의 각 값 b에 대해:
        tp[b]가 0이 아니면 다음 반복으로 건너뜀
        dfs(b, k)

res := 0
i := 0부터 n 미만까지 반복:
    seq[i]가 i와 같으면 res 1 증가

i := 0부터 m 미만까지 반복:
    a := pairs[i]의 첫 번째 값
    b := pairs[i]의 두 번째 값
    vis[a]의 끝에 b 삽입
    vis[b]의 끝에 a 삽입

idx := 1
i := 0부터 n 미만까지 반복:
    tp[i]가 0이면:
        dfs(i, idx)
        vtmp[idx]의 각 원소 j에 대해:
            tp[seq[j]]가 idx와 같고 seq[j] ≠ j이면 res 1 증가
        idx 1 증가

res 출력

C++ 구현 예제

아래 구현을 통해 동작 방식을 더 잘 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
#define N 100
int tp[N];
vector<int> vtmp[N], vis[N];
void dfs(int j, int k){
    tp[j] = k;
    vtmp[k].push_back(j);
    for(auto b : vis[j]) {
        if(tp[b] != 0)
            continue;
        dfs(b, k);
    }
}
void solve(int n, int m, int seq[], vector<pair<int, int>> pairs) {
    int res = 0;
    for(int i = 0; i < n; i++){
        if(seq[i] == i)
            res++;
    }
    for(int i = 0; i < m; i++){
        int a = pairs[i].first;
        int b = pairs[i].second;
        vis[a].push_back(b);
        vis[b].push_back(a);
    }
    int idx = 1;
    for(int i = 0; i < n; i++) {
        if(tp[i] == 0) {
            dfs(i, idx);
            for(auto j: vtmp[idx]){
                if(tp[seq[j]] == idx && seq[j] != j)
                    res++;
            }
            idx++;
        }
    }
    cout << res;
}
int main() {
    int n = 4, m = 2, seq[] = {0, 3, 2, 1};
    vector<pair<int,int>> pairs = {{0, 1}, {2, 3}};
    solve(n, m, seq, pairs);
    return 0;
}

입력

4, 2, {0, 3, 2, 1}, {{0, 1}, {2, 3}}

출력

2

동작 원리 살펴보기

예제에서 인덱스 0과 1은 pairs를 통해 연결되어 있고, 2와 3 역시 서로 연결되어 있습니다. 초기 상태에서 seq[0] = 0, seq[2] = 2이므로 이미 두 개의 고정점이 존재합니다. 첫 번째 연결 요소 {0, 1}에서 seq[1] = 3인데, 3은 두 번째 연결 요소에 속한 값이므로 제자리로 옮길 수 없습니다. 마찬가지로 두 번째 연결 요소 {2, 3}에서 seq[3] = 1 역시 첫 번째 연결 요소에 속하므로 교환이 불가능합니다. 따라서 최종 답은 2가 됩니다.