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

📕문제

---

세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1 이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절히 뽑으면, 그 뽑힌 정수들이 이루는 집합과, 뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이 일치한다. 이러한 조건을 만족시키도록 정수들을 뽑되, 최대로 많이 뽑는 방법을 찾는 프로그램을 작성하시오. 예를 들어, N=7인 경우 아래와 같이 표가 주어졌다고 하자.

이 경우에는 첫째 줄에서 1, 3, 5를 뽑는 것이 답이다. 첫째 줄의 1, 3, 5밑에는 각각 3, 1, 5가 있으며 두 집합은 일치한다. 이때 집합의 크기는 3이다. 만약 첫째 줄에서 1과 3을 뽑으면, 이들 바로 밑에는 정수 3과 1이 있으므로 두 집합이 일치한다. 그러나, 이 경우에 뽑힌 정수의 개수는 최대가 아니므로 답이 될 수 없다.

📕입력

---

첫째 줄에는 N(1≤N≤100)을 나타내는 정수 하나가 주어진다. 그 다음 줄부터는 표의 둘째 줄에 들어가는 정수들이 순서대로 한 줄에 하나씩 입력된다.

📕출력

---

첫째 줄에 뽑힌 정수들의 개수를 출력하고, 그 다음 줄부터는 뽑힌 정수들을 작은 수부터 큰 수의 순서로 한 줄에 하나씩 출력한다.

🔎문제 해석

---

문제를 보면 일단 DFS로 풀어야 한다는 것을 감을 잡았다면 여러분은 DFS, BFS를 많이 풀어봤다는 뜻입니다.

하지만 다른 DFS문제랑은 조금은(?) 다르다는 것을 알아야 합니다. 

 

예시를 testcase로 잡고 설명해보겠습니다.

아래의 입력이 Testcase입니다.

1	2	3	4	5	6	7
3	1	1	5	5	4	6

1. 조합이 일치하는 최대의 수를 뽑아야 하는 것이 문제의 목표입니다. (1번부터 시작한다고 가정)
2. 1번은 아래의 숫자가 3이다.
3. 그럼 우리는 위의 숫자중 3번을 타고 들어가서 3번 아래의 숫자가 1인지를 확인해야 한다. 
   • 1이라면 다시 되돌아갈수 있으므로, 조합에 1과 3을 추가하면 된다.
   • 만약 1이 아니라 다른 숫자라면? 2번과 3번 과정을 다시 거쳐서 확인을 해야 한다.

즉 쉽게 설명하면 배열[i] -> 배열[배열[i]] -> 배열[배열[배열[i] ] ] -> 쭉쭉 가다 보면 방문했던 숫자에 다시 방문하게 되는 경우가 발생할 것입니다. 방문했던 숫자에 다시 방문한다면 그때가 적절한 조합입니다.

 

💡예를 들어서

1. 1번 시작 :1->3->1->3 == (1,3)은 적절한 조합입니다!
2. 2번 시작:  2->1->3->1->3->1 == 2번으로 되돌아가지 못하고, 1,3번은 각각 되돌아가기에 (1,3)이 추가됩니다.
3. 3번 시작 : 3->1->3->1이기 때문에 (1,3)이 추가
4. 4번 시작 : 4->5->5->5이기 때문에 (5) 추가
5. 5번 시작 : 5->5이기 때문에 (5) 추가
6. 6번 시작 : 6->4->5->5->5이기 때문에 (5) 추가
7. 7번 시작 : 7->6->4->5->5->5이기 때문에 (5) 추가 

💡또 다른 예로는 

1	2	3
2	3	1

1. 1번 시작 : 1->2->3->1->2->3  (1,2,3) 추가
2. 2번 시작 : 2->3->1->2->3->1 (1,2,3) 추가
3. 3번 시작 : 3->1->2->3->1->2 (1,2,3) 추가

추가할 때는 중복을 원하지 않았기 때문에 map에다 각 원소를 넣어줬다.

(지금 생각해보면 굳이 map 아니고 set에 넣어도 됐을 거은,,,)

 

📃코드 단계

• 모든 좌표에 대해서 dfs를 실행합니다.
• 출발 좌표에서 dfs로 탐색하여 방문했던 숫자에 다시 방문했을 경우, 다시 출발 좌표로 되돌아 오는지를 체크한다.
  • 다시 출발 좌표로 돌아왔다면 따로 check해서, 그때 호출 내에서 방문했던 숫자들을 map에 추가한다.
  • 다시 출발좌표로 돌아오지 못한 경우는 같은 조합을 만들어내지 못하는 숫자 조합이기에 추가하지 않는다.

 

💻코드

/*
골드5 2688 숫자 고르기
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
using namespace std;
int n, C = 0, result = 0;
vector<int> graph;
vector<int> visit;
map<int, int> m;
bool check;
void dfs(int x, int fx);
int main()
{
    cin >> n;
    graph.resize(n + 1, 0);
    visit.resize(n + 1, 0);
    for (int i = 1; i <= n; i++)
    {
        cin>>graph[i];
    }
    for (int i = 1; i <= n; i++)
    {
        visit[i] = 1; //현재 탐색 좌표 방문 처리
        dfs(i, graph[i]); 
        visit.assign(n + 1, 0); //방문 초기화
        check = false; // 초기화
    }
    cout << m.size() << endl;
    for (auto a : m)
    {
        cout << a.first << endl;
    }
}
void dfs(int x, int fx)
{
    if (visit[fx])
    { //이미 방문했다면
        if (x == fx) //다시 되돌아갔다면 
        {
            check = true; //check를 true로 바꿔줌
            m.insert(make_pair(fx, 0)); //그때의 값을 map에다 넣어줌.
        }
        return; //다시 돌아가지 않았따면
    }
    //방문안햇다면
    visit[fx] = 1;
    dfs(x, graph[fx]);
    if (check) //만약 dfs를 탈출했을때 check가 true라면,  두 좌표는 조합이 일치하기 때문에 넣어줌.
    {
        m.insert(make_pair(fx, 0));
        m.insert(make_pair(graph[fx], 0));
    }
}

 

 

✔느낀 점

1. 이때까지 풀었던 DFS랑은 조금 달라서 많이 헷갈리고 오래 걸렸습니다.
2. 문제가 너무 이해하기 어렵고 재귀 과정에서 엄청 복잡했다.
3. 손으로 ㅈㄴ그렸다.
4. 중복을 허용하지 않는다면 더 효율적인 자료형은 set이야 재한아. 기억해!!
5. 중복을 허용하지 않는다면 더 효율적인 자료형은 set이야 재한아. 기억해!!
6. 중복을 허용하지 않는다면 더 효율적인 자료형은 set이야 재한아. 기억해!!
7. 중복을 허용하지 않는다면 더 효율적인 자료형은 set이야 재한아. 기억해!!
8. 중복을 허용하지 않는다면 더 효율적인 자료형은 set이야 재한아. 기억해!!
9. 중복을 허용하지 않는다면 더 효율적인 자료형은 set이야 재한아. 기억해!!
10. 중복을 허용하지 않는다면 더 효율적인 자료형은 set이야 재한아. 기억해!!