코딩테스트/문제

[백준] 3182번 한동이는 공부가 하기 싫어!

스키(ski) 2022. 9. 2. 03:57
문제 내용

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

 

3182번: 한동이는 공부가 하기 싫어!

H-ALGO 회원인 한동이는 공부하는것을 좋아하지 않는다. 하지만 약삭빠르게도 한동이는 공부도 하지 않으면서 어려운 시험을 통과하고 싶어한다. 그러던 와중 어느 날, 한동이의 동기가 한동이에

www.acmicpc.net

해결 코드
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
#include <iostream>
#include <string.h>
 
#define MAX_N 1001
 
using namespace std;
 
int n;
bool arr[MAX_N][MAX_N];
bool visited[MAX_N];
 
int DFS(int idx) {
    visited[idx] = true;
 
    for (int i = 1; i <= n; i++) {
        if (arr[idx][i] && !visited[i])
            return 1 + DFS(i);
    }
 
    return 1;
}
 
int main() {
    int max = 0;
    int idx = 0;
    cin >> n;
 
    for (int i = 1; i <= n; i++) {
        int a;
        cin >> a;
 
        arr[i][a] = true//단방향 그래프
    }
 
    for (int i = 1; i <= n; i++) {
        int find = DFS(i);
 
        if (max < find) {
            max = find;
            idx = i;
        }
 
        memset(visited, false, MAX_N * sizeof(bool)); // 매 케이스마다 초기화
    }
 
    cout << idx;
}
 
cs

 

주요 개념 
  • 그래프 탐색: 깊이 우선 탐색(Depth-First Search,DFS)

 

주의 사항
  1. 해당 문제는 단방향 그래프라는것을 고려

'코딩테스트 > 문제' 카테고리의 다른 글

[백준] 2805번 나무 자르기  (0) 2023.07.03
[백준] 11724번 연결 요소의 개수  (0) 2023.06.28
[백준] 16928번 뱀과 사다리 게임  (0) 2022.09.04
[백준] 9019번 DSLR  (0) 2022.09.03
[백준] 1107번 리모컨  (0) 2022.09.02