[SWEA 8424][C++] 유일한 사이클 (D4)

[문제보기]

 8424. 유일한 사이클

SW Expert Academy

 

[풀이과정]

그래프를 이용하여 문제를 풀었다.

vector<vector<int>> v를 사용하여 각 노드당 간선을 만들어준다. (무방향 그래프이므로 각 노드마다 넣어줘야한다)

그리고 완전 탐색을 통해 사이클을 찾아주는데, 파라미터로 (int prev, int cur, int depth)를 준다.

처음에 각 노드에 해당하는 check[]의 값은 '0'으로 주어지고, node를 지나갈 때마다 depth가 주어진다.

 

prev는 각 노드에서 간선을 통해 다른 노드로 넘어가는데, 이 때 자신이 왔던 길을 다시 지나가지 않기 위함이다.

 

현재 노드에서 다음 노드가 이전의 노드가 아니고, check에 값을 가지고 있다면, 사이클이 완성된 것이다.

check[cur] - check[next] + 1를 통해 사이클의 크기를 구해준다.

 

- 문제에서 만들어지는 사이클은 하나만 있다고 하므로 ans이 '0'이 아닌 값을 가지게 되면 완전 탐색을 끝내준다.

 

[소스보기]

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
vector<vector<int>> v;
int n, ans = 0;
int check[1001];

void DFS(int prev, int cur, int depth){
    check[cur] = depth;
    for(int i=0; i<v[cur].size(); i++){
        int next = v[cur][i];
        if(ans != 0){
            return;
        }
        if(check[next] != 0){
            if(next != prev){
                ans = check[cur] - check[next] +1;
                return;
            }
        }
        else{
            DFS(cur, next, depth+1);
        }
    }
}


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

    int T;
    cin >> T;
    for(int test = 1; test <= T; test++){
        ans = 0;
        cin >> n;
        v = vector<vector<int>>(n+1, vector<int>());
        memset(check, 0, sizeof(check));

        for(int i=0; i<n; i++){
            int x, y;
            cin >> x >> y;
            v[x].push_back(y);
            v[y].push_back(x);
        }

        DFS(0, 1, 1);

        cout << "#" << test << " " << ans << "\n";
    }
}

 

[해결 과정 중 실수한 부분]

이 문제는 예전에 스터디에서 풀었던 문제였지만, 그 때 당시 check를 bool형태로 주면서 이 변수로 구별을 할려니 

사이클을 찾는데 불가능했다. (지나온 노드를 false에서 true로 바꾸어 줬을 때, 다음 노드가 

왔던 노드이기 때문에 true인지, 사이클이 만들어져 true인지를 구별 불가)

 

하지만 파라미터로 int prev, int cur를 주면서, 이를 이용해 자기가 왔던 노드를 알 수 있기 때문에, 구별을 할 수 있게

되었다.  그리고 check[] 변수를 int형으로 주고, 각 노드의 깊이를 주어짐으로 인해 사이클의 크기도 알 수 있게 되었다.