백준 2668 - 숫자고르기(C++)

 

문제 링크입니다. https://www.acmicpc.net/problem/2668

2668번: 숫자고르기

DFS를 이용해 푸는 문제입니다.

윗 줄의 숫자를 하나씩 선택할 때마다, 밑에 붙어 있는 숫자도 같이 선택됩니다.

윗 줄의 숫자를 선택해, 밑의 줄의 숫자와 같게 뽑으려고 할 때 몇 개, 어떤 숫자를 뽑아야하는지 구하는 문제입니다.

 

이 문제를 푸는 핵심은 윗 줄과 아랫 줄의 숫자를 연결해주는 겁니다.

만약 윗 줄이 1, 아랫 줄이 3이라면, connect[1] = 3 으로 서로 연결해주는 것을 의미합니다.

 

그 다음, 숫자를 선택할 차례입니다. 한번의 기회만 있는 것이 아닌, 여러 번의 숫자를 뽑아도 됩니다.

문제 에시를 본다면, (1, 3) 과 (5)를 나눠 뽑은 것을 확인할 수 있습니다.

따라서, 1부터 N의 값까지 어떤 수를 뽑을 수 있는지 확인해주면 됩니다.

 

i값을 통해 탐색할 때, 탐색하는 방법입니다.

1. 윗줄의 값을 선택한 뒤, 밑줄의 값을 확인합니다.

2. 밑줄의 값을 가지고 있는 윗 줄의 숫자를 선택합니다.

3. 선택한 숫자의 밑줄의 숫자를 확인합니다.

-> 해당 방법을 반복해주면 됩니다.

 

이렇게 탐색을 할 때, 끝나는 조건은 처음에 선택한 값과 나중에 선택하는 값이 같을 때입니다. 그렇다는 의미는 아랫 줄과 윗 줄이 서로 같은 값으로만 구성되었다는 의미이기 때문입니다.

 

 

자세한 것은 코드를 참고해주세요

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#define P pair<int, int>
#define F first
#define S second
using namespace std;

int N, ans;
int connect[101];
int check[101];
vector<int> Select;
vector<int> num;

void dfs(int start, int N, int cnt){
    check[start] = 1;
    Select.push_back(start);
    if(cnt > 0 && start == N){
        num.insert(num.end(), Select.begin(), Select.end());
        return;
    }
    if(check[connect[start]] == 0){
        dfs(connect[start], N, cnt+1);
    }
}

void solve(){
   for(int i = 1; i <= N; i++){
        Select.clear();  
        memset(check, 0, sizeof(check));
        if(check[i] == 0) dfs(connect[i], i, 1);
    }
    sort(num.begin(), num.end());
    num.erase(unique(num.begin(), num.end()), num.end());
    cout << num.size() << "\n";
    for(int i = 0; i < num.size(); i++) cout << num[i] << "\n";
}

int main(){
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    for(int i = 1; i <= N; i++){
        int x;
        cin >> x;
        connect[i] = x;
    }
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요