반응형

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

 

2668번: 숫자고르기

세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. arr 배열에 수들을 입력받습니다.

 

2. dfs를 통해서 방문하는 노드마다 경로를 저장하고, 사이클이 생긴다면 해당 지점부터 모든 사이클을 ans 배열에 저장합니다.

 

3. ans 배열의 값이 1이라면 해당 인덱스를 출력합니다.

 

[ 소스코드 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<iostream>
#include<vector>
 
using namespace std;
 
int N;
int arr[101];
int visited[101];
int ans[101];
vector<int> box;
int cnt;
 
void dfs(int cur)
{
    if (ans[cur] == 1) return;
 
    if (visited[cur] == 1) {
        bool flag = false;
        for (auto& next : box) {
            if (next == cur) {
                flag = true;
            }
            if (flag == true) {
                ans[next] = 1;
                cnt++;
            }
        }
        box.clear();
        return;
    }
    box.push_back(cur);
 
    visited[cur] = 1;
    dfs(arr[cur]);
    
    return;
}
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 1; i <= N; i++) {
        scanf("%d", &arr[i]);
    }
 
    for (int i = 1; i <= N; i++) {
        if (ans[i] != 1) {
            fill(visited, visited + N + 1, 0);
            dfs(i);
        }
    }
 
    printf("%d\n", cnt);
 
    for (int i = 1; i <= N; i++) {
        if (ans[i] == 1) {
            printf("%d\n", i);
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 2602번 - 돌다리 건너기 (C++)  (0) 2023.04.18
[ 백준 ] 1507번 - 궁금한 민호 (C++)  (0) 2023.04.17
[ 백준 ] 1253번 - 좋다 (C++)  (0) 2023.04.15
[ 백준 ] 2749번 - 피보나치 수 3 (C++)  (0) 2023.04.14
[ 백준 ] 2436번 - 공약수 (C++)  (0) 2023.04.13

+ Recent posts

티스토리툴바