문제 내용
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)
주의 사항
- 해당 문제는 단방향 그래프라는것을 고려
'코딩테스트 > 문제' 카테고리의 다른 글
[백준] 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 |