백준 - 9466 텀 프로젝트

 

해결과정 - 사이클 찾기

단순 사이클 찾기 문제라는 것을 깨닳고 재귀를 사용하려고 했으나 비슷한 유형의 문제를 너무 많이 풀어봐서 이번에는 반복문으로 해결해 보고 싶다는 생각이 들었다. 그래서 배열 담는 용도인 arr, 방문체크 목적인 visited, 사이클의 원소 수를 체크하기 위한 depth 배열을 구성하였다. 여기에서 visited의 값으로 현재 순환중인 노드의 첫번째 값 예를들어 1번째 노드부터 시작하여 순환하고 있으면 1번째 노드의 값을 넣어줌으로 써 다음번 순회를 돌경우 방문한 곳이 사이클로인해 방문한 곳인지 아님 전에 방문하여 못가는 곳인지 체크하도록 하였다

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

#define FAST ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)

typedef long long ll;

using namespace std;


int main() {
    FAST;

    int T;
    cin >> T;

    while (T--) {
        int n;
        cin >> n;

        vector<int> arr(n + 1);
        vector<int> depth(n + 1, 0);

        for (int i = 1; i <= n; i++) {
			cin >> arr[i];            
		}

        vector<int> visited(n + 1);
        int result = 0;

        for (int i = 1; i <= n; i++) {
            if (visited[i]) continue;

            int cur = i;
            int de = 1;
            visited[cur] = i;
            depth[cur] = de++;

            while (true) {
                int next = arr[cur];

                if (visited[next] == i) {
                    result += depth[cur] - depth[next] + 1;
                    break;
                }
                else if (visited[next]) {
                    break;
                }

                depth[next] = de++;
                visited[next] = i;
                cur = next;
            }
        }

        cout << n - result << '\n';
    }
    return 0;
}

 

후기

그래프 문제는 내 기준으로 골드는 2단계정도 낮춰야 될거 같다

dp 골드문제는 여전히 어렵지만 열심히 풀다보면 이또한 쉬워지지 않을까