[백준/Baekjoon] 9466 텀 프로젝트 C++ :: DFS & Graph

https://www.acmicpc.net/problem/9466

9466번: 텀 프로젝트

---

1. Logic

처음에 문제를 봤을 때 유니온 파인드로 푸는 줄 알았다. 정 안풀려서 블로그를 참고해서 풀이했다,,

 

r1-r2, rn-r1 끼리 팀을 맺는다는 말은 순환이 있는 그래프끼리 팀을 맺는다는 말이다. 

재귀를 활용해서 vis배열에 방문을 처리하면서 방문처리된 배열에 group배열(그룹이 만들어졌다는, 순환하는 그래프의 노드를 표시)이 false라면 그룹을 만들 수 있는 상황이기 때문에 연결된 노드들을 group배열에 방문 처리 해준다.

1-2, 2-4, 4-1이면 1, 2, 4는 서로 그룹이 될 수 있다.

1-2를 방문하고 2-4 방문하고 4-1을 방문했을 때 1번은 이미 방문처리가 됐지만 group배열에는 확인이 안됐기 때문에 그룹이라는 것을 알고 cnt 해준다.

---

 

2. Code

#include <bits/stdc++.h>

using namespace std;

int node[100001];
bool group[100001];
bool vis[100001];

int n;
int ans;

void solve(int firstChoice) {
    vis[firstChoice] = true;
    int next = node[firstChoice];
    
    if(!vis[next]){ 
        solve(next);
    }
    else if(!group[next]) {
        for(int i = next; i != firstChoice; i = node[i])  {
            ans++;
        }
        ans++;
    }
    
    group[firstChoice] = true;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    int t;
    cin >> t;
    
    while(t--) {
        cout << "here" << "\n";
        memset(vis, false, sizeof(vis));
        memset(group, false, sizeof(node));
        ans = 0;
        
        cin >> n;
        
        for(int i = 1; i <= n; i++) {
            cin >> node[i];
        }
        
        for(int i = 1; i <= n; i++) {
            if(vis[i]) continue;
            solve(i);
        }
        
        cout << n - ans << "\n";
    }
}

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐

728x90