[백준] 9466번: 텀 프로젝트 (C++)

 

원하는 상대를 저장하는 arr

방문 여부를 나타내는 visited

그룹이 확정된 상태를 나타내는 done

총 세 가지 배열을 사용하여 구현하였다

 

방문 여부를 먼저 탐색한 후 

방문 했다면 짝이 이루어져있는지 확인한다

이후 과정을 dfs로 반복한다

이후 배열의 크기에서 조가 짜여진 사람 수를 뺀 값을 출력한다

 

자잘한 과정의 흔적(?)을 보면

void reset()을 구현하는 대신 memset을 통해 초기화할 수 있다

 

for 문이 꼭 하나씩 커지도록 선언하지 않더라도 동작한다

 

또한 select의 s를 소문자로 사용했을 때 

pc의 컴파일러에서는 잘 작동했지만

백준에 제출했을 때는 중복된 함수 이름으로 컴파일 에러가 발생했다

백준에서 select 라는 이름의 변수를 선언할 때는 유의해야한다

// baekjoon 9466

#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;

// codes for fast I/O
void init(){
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(false);
}


int arr[100001];
bool visited[100001];
bool done[100001];

int N, Select;


// DFS
void dfs(int num){
    visited[num] = true;
    
    int next = arr[num];
    
    if(!visited[next]){
        dfs(next);
    }
    
    else if(!done[next]){
        for(int i = next; i != num; i = arr[i]){
            Select++;
        }
        Select++;
    }
    
    done[num] = true;
}


int main(){
    init();
    
    int T;
    cin >> T;
    
    for(int i = 0; i < T; i++){
        
        memset(visited, false, sizeof(visited));
        memset(done, false, sizeof(done));
        
        cin >> N;
        
        for(int j = 1; j <= N; j++){
            cin >> arr[j];
        }
        
        Select = 0;
        
        for(int j = 1; j <= N; j++){
            if(!visited[j]){
                dfs(j);
            }
        }
        
        cout << N - Select <<'\n';
    }
    
    return 0;
}

참고 사이트

백준 9466 텀 프로젝트 c++ (dfs) (tistory.com)