[BOJ][골5][2668] 숫자고르기

문제 링크

문제링크

첫 번째 풀이 : DFS

알고리즘

각 노드에서 dsf를 시작해서 싸이클이 있는지 판단합니다. 그리고 모든 싸이클의 원소 집합이 정답입니다.

1 - 3 - 5까지 진행된 dfs에서 5 다음의 노드가

1. 1 이라면 정답에 포함되어야 합니다.
2. 3 또는 5라면 dfs 를 중단해야 합니다.

1.번 경우인지 판단하기 위해서 recur에 start와 curr를 인자로 전달합니다. 2.번 경우는 visited를 사용해서 이미 방문된 노드인지 판단합니다.

예시의 5번과 같이 자신으로 바로 이어지는 싸이클이 먼저 선택된 경우도 고려해봐야 합니다. 1이 단독 싸이클로 선택된 경우 2 - 3 - 5까지 dfs가 진행되었을 때, 5 다음 노드가

1. 2라면 정답에 포함되어야 합니다.
2. 1,3,5라면 dfs를 중단해야 합니다.

이 경우도 마찬가지의 방법으로 해결할 수 있습니다.

정답 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, k;

int arr[101];
bool visited[101];

vector<int> ans;
vector<int> selected;

// curr가 방문 안했으면 selected에 넣고 next로 이동
// curr가 방문했으면 처음과 같은지 판단
bool dfs(int start, int curr) {
  if (!visited[curr]) {
    visited[curr] = true;
    selected.push_back(curr);
    int next = arr[curr];
    return dfs(start, next);
  }else{
    return curr == start;
  }
}


int main()
{
  //freopen("input.txt", "r", stdin);
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> n;

  for (int i = 1; i <=n; i++) {
    cin >> arr[i];
  }
  
  memset(visited, false, sizeof(visited));
  for (int i = 1; i <= n; i++) {
    if (visited[i]) continue;
    if (dfs(i, i)) { //i에서 i로 끝나는 싸이클인 경우
      // 방문한 값들을 정답 집합에 보관하기
      while (!selected.empty()) {
        ans.push_back(selected.back());
        selected.pop_back();
      }
    }else{ //싸이클이 아닌 경우
      // 선택된 원소들을 방문처리 해제
      for (int j = 0; j < selected.size(); j++) {
        visited[selected[j]] = false;
      }
      selected.clear();
    }
  }
  // 정렬 후 출력
  cout << ans.size() << "\n";
  sort(ans.begin(), ans.end());
  for (int i = 0; i < ans.size(); i++) {
    cout << ans[i] << "\n";
  }
  return 0;
}

Success Notice: 수고하셨습니다.