[ 백준 ] 2668 / 숫자고르기

金弘均·2021년 9월 16일
0

Baekjoon Online Judge

목록 보기
203/228
post-thumbnail

# Appreciation

/*
 * Problem :: 2668 / 숫자고르
 *
 * Kind :: DFS
 *
 * Insight
 * - 첫째줄에서 뽑힌 정수들이 이루는 집합(set)과 <= A (a1, a2, ..., an)
 *   뽑힌 정수들의 둘째 줄에 들어있는 정수들이 이루는 집합(set)이 <= B (b1, b2, ..., bn)
 *   서로 같아야 된다
 *   + A = B 이니 (집합을 이루는 원소가 모두 같으니)
 *     첫째 줄의 a1, a2, ..., an 은
 *     모두 서로다른 b1, b2, ..., bn 을 둘째 줄에 가져야 한다
 *     # 첫째 줄에 a1 이 있고 둘째 줄에 b1 이 있다고 하자
 *       A = B 이므로 b1 값과 같은 원소가 A 에 있을 것이다, 이를 a2 라고 하자
 *       그렇다면 첫째 줄에 a2 가 있고 둘째 줄에는 또 어떤 값을 가진 bn 이 있을 것이다
 *       이를 b2 라고 하자
 *       A = B 이므로 b2 값과 같은 원소가 A 에 있을 것이다, 이를 a3 라고 하자
 *       그렇다면 첫째 줄에 a3 가 있고 둘째 줄에는 또 어떤 값을 가진 bn 이 있을 것이다
 *       이를 b3 라고 하자
 *       ...
 *       -> (a1 -> b1)
 *          (a2=b1 -> b2)
 *          (a3=b2 -> b3)
 *          ...
 *          이를 일반화해서
 *          (ax=bx-1 -> bx) 라고 하자
 *          A = B 이려면 언젠가는 bx 가 a1 이 되어야 한다!!!
 *          즉, 사이클이 되어야 하는 것이다!!!
 *          각 숫자를 노드로, 첫째 줄의 노드에서 둘째 줄의 노드 사이의 간선이라고 생각하면
 *          이들이 사이클이 되어야 A = B 가 성립한다!!!
 *
 * - 1 2 3 4 5 6 7
 *   3 1 1 5 5 4 6
 *   + 각 숫자를 노드라고 생각하고
 *     각 열의 첫째 줄에서 둘째 줄로 간선이 연결된다고 생각하면
 *     총 1->3, 2->1, 3->1, 4->5, 5->5, 6->4, 7->6
 *     (1,3) = 1->3, 3->1
 *     (5) = 5->5
 *     # 답은 (1,3,5) 이니 가능한 모든 사이클을 더해주자
 *
 * Point
 * - 수학적으로 더 엄밀하게 증명할 수 있는 것 같은데...
 *   주석으로만 할려니 기호넣기가 참 힘들고 귀찮다
 *   + 문제를 처음 접했을 때 어떻게 풀이를 떠올렸는지
 *     Insight 를 정리하는 목적으로 글을 쓰는 것이니까
 *     귀엽게 봐줄 수 있지 않을까? (헤헷) <= 합리화보소
 *
 * - 사이클 판별할 때
 *   코드에서는 시작노드와 마지막노드를 가지고 비교해주었다
 *   + 1 -> 2 -> 3
 *          ^    |
 *          |    V
 *          5 <- 4
 *     코드에서 사용된 로직으로는 1 과 2 를 방문해야하지만
 *     사실 1 만 방문하더라도 (2,3,4,5) 가 사이클임을 알 수 있고
 *     (1,2,3,4,5) 를 방문처리하는 최적화를 적용해볼 수 있다
 *     # 그런데 N=100 이라서 굳이 위와같은 최적화까지는 필요하지 않을 것 같아 적용하지 않았다
 *       -> 처음에 풀었던 코드에서는 그렇게 했는데...
 *          사실 가독성이 더 떨어지는 것 같아서...
 *          
 * - DFS 가 맞긴 한데 <= 깊이 우선 탐색
 *   문제 특성상 노드 간의 간선이 1개라
 *   그냥 배열로 다루어주었다 (Vector 안 쓰는 DFS 라니 신선하다)
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <set>
#include <cstring>

using namespace std;

#define endl '\n'

// Set up : Global Variables
/* None */

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int N; cin >> N;
    int A[N+1];
    for (int i=1; i<=N; i++)
        cin >> A[i]; /* A[i] = 첫째줄 i, 둘째줄 A[i] */

    // Process
    bool isCycle[N+1];
    memset(isCycle, false, sizeof(isCycle));
    set<int> ans; /* 사이클인 모든 노드들이 저장되는 Set */
    for (int i=1; i<=N; i++) {
        /* 시작 숫자(노드) : i */
        /* i 가 이미 사이클에 포함되는 노드로 밝혀 졌다면 다음 숫자로 넘어감 */
        if (isCycle[i]) continue;

        set<int> s; /* DFS 에서 방문한 노드들이 저장되는 Set */
        s.insert(i); /* 시작 노드 추가 */
        int n = A[i]; /* 다음 노드 */
        while (true) {
            /* 시작 노드를 다시 만나면 지금까지 방문한 노드들은 사이클임 */
            if (n == i) {
                ans.insert(s.begin(), s.end()); /* ans 에 추가 */
                /* 방문한 노드들을 사이클에 포함되는 노드들로 체크 */
                for (int e : s) { isCycle[e] = true; }
                break; /* DFS 종료 */
            }

            /* 시작 노드를 다시 만나지 않았는데 지금까지 방문한 노드들 중 하나를 다시 만나면
             * 이는 시작 노드를 포함하는 사이클이 아니라는 뜻이니 DFS 종료 */
            if (s.find(n) != s.end()) break;
            s.insert(n); /* 다음 노드를 방문한 노드에 추가 */
            n = A[n]; /* 다음 노드 갱신 */
        }
    }

    // Control : Output
    cout << ans.size() << endl;
    for (int n : ans) {
        cout << n << endl;
    }
}

// Helper Functions
/* None */
profile
이런 미친 게임을 봤나! - 옥냥이

0개의 댓글