[그래프(사이클)] 해커랭크 Minimum swap C++

중복 없는 숫자

(사이클 크기 - 1)의 합

사이클 내에서 무조건 한 칸씩 이동

Union-Find or Set 이용 가능

// 횟수만 체크
int minimumSwaps(vector<int> arr) {
    int answer = 0;
    vector<bool> visited(arr.size(), false);
    for(int i=0; i<arr.size(); i++) {
        if (visited[i]) continue;
        int x = i;
        while (true) {
            visited[x] = true;
            answer++;
            x = arr[x] - 1;
            if (x == i) break;
        }
        answer--;
    }
    return answer;
}

// 배열 교환
int minimumSwaps(vector<int> arr) {
    int answer = 0;
    for(int i=0; i<arr.size(); i++) {
        if (i == arr[i] - 1) continue;
        int x = i;
        while (true) {
            swap(arr[x], arr[arr[x] - 1]);
            answer++;
            if (x == arr[x] - 1) break;
        }
    }
    return answer;
}

int minimumSwaps(vector<int> arr) {
    int answer = 0;
    for(int i=0; i<arr.size(); i++) {
        if (i == arr[i] - 1) continue;
        swap(arr[i], arr[arr[i]-1]);
        answer++;
        i--;
    }
    return answer;
}

// 선택정렬 교환 횟수(O(N^2) 시간초과)
int minimumSwaps(vector<int> arr) {
    int answer = 0;
    for(int i=0; i<arr.size(); i++) {
        int idx = i;
        for(int j=i+1; j<arr.size(); j++) {
            if (arr[idx] > arr[j]) idx = j;
        }
        if (idx != i) {
            swap(arr[i], arr[idx]);
            answer++;
        }
    }
    return answer;
}

#include <iostream>
#define N 7

using namespace std;

// 012345 -> 031254
// 325104 -> 312540

int order[N] = {5, 2, 1, 4, 3, 6, 0};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int answer = 0;
    bool visited[N] = {false};
    for(int i=0; i<N; i++) {
        if (visited[i]) continue;
        int x = i;
        while (true) {
            visited[x] = true;
            answer++;
            x = order[x];
            if (x == i) break;
        }
        answer--;
    }

    cout << answer;

    return 0;
}

#include <iostream>

using namespace std;

int parent[6];
int arr[6] = {1, 1, 2, 2, 1, 1};
int order[6] = {3, 2, 5, 1, 0, 4}; // 012345 -> 325104 = 221111, 1, 0, 5, 2, 3, 4

int answer;
bool visited[6];

int find(int x) {
    if (parent[x] < 0) return x;
    return parent[x] = find(parent[x]);
}

void merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    if (parent[x] > parent[y]) swap(x, y); // if (x > y) swap(x, y);
    parent[x] = min(parent[x], parent[y] - 1);
    parent[y] = x; // 순서 조심
}

void dfs(int x) {
    if (visited[x]) return;
    visited[x] = true;
    answer++;
    dfs(order[x]);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    for(int i=0; i<6; i++) parent[i] = -1;

    for(int i=0; i<6; i++) {
        if (find(i) != find(order[i])) merge(i, order[i]);
    }

    for(int i=0; i<6; i++) cout << parent[i];
    cout << "\n";

    for(int i=0; i<6; i++) {
        if (parent[i] < 0) {
            dfs(i);
            answer--;
        }
    }

    cout << answer;

    return 0;
}

중복 있는 숫자

투포인터

#include <iostream>
#define N 6

using namespace std;

// 012345 -> 031254 / 112211 -> 121211
// 325104 -> 312540 / 221111 -> 212111

int arr[N] = {1, 1, 2, 2, 1, 1};
int order[N] = {3, 2, 5, 0, 1, 4};
int parent[N];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    for(int i=0; i<N; i++) cout << arr[i];
    cout << "\n";

    for(int i=0; i<N; i++) parent[order[i]] = i;

    int answer = 0;
    bool visited[N] = {false};
    for(int i=0; i<N; i++) {
        if (visited[i]) continue;
        
        int start = i;
        int end = parent[i];

        while (true) {
            visited[start] = true;
            visited[end] = true;
            if (arr[start] != arr[end]) {
                swap(arr[start], arr[end]);
                answer++;
            }
            if (arr[start] == arr[order[start]]) start = order[start];
            end = parent[end];
            if (start == end) break;
        }
    }

    for(int i=0; i<N; i++) cout << arr[i];
    cout << "\n";

    cout << answer;

    return 0;
}