Notice
Recent Posts
Recent Comments
Link
«   2024/03   »
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
Archives
Today
Total
관리 메뉴

차근차근

[백준 1325] 효율적인 해킹 본문

대학교/Algorithm

[백준 1325] 효율적인 해킹

SWKo 2020. 2. 26. 16:55

0. 제목

  • 백준 1325 효율적인 해킹
  • BOJ 1325 효율적인 해킹
  • C++ 1325 효율적인 해킹

1. 문제

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


2. 풀이

  • 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 것이 문제이다.
  • dfs를 사용하여 연결되어 있는 컴퓨터의 수를 센다.
  • 각 컴퓨터를 시작점으로 dfs를 시행하여 컴퓨터 수를 세고 그것을 depth배열에 담는다.
  • depth배열의 원소 중 최댓값을 구한다.
  • depth배열의 원소 값 중 최댓값과 같은 값을 가지고 있는 index들을 순서대로 출력한다.

3. 코드

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
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
 
vector<int> v[10001];
int visited[10001];
int cnt;
 
void dfs(int x){
    if(visited[x]) return;
    visited[x] = true;
    cnt++;
    for(int i = 0; i < v[x].size(); i++){
        int y = v[x][i];
        dfs(y);
    }
}
 
int main(int argc, const char * argv[]) {
    int N, M;
    cin >> N >> M;
    
    int a, b;
    for(int i = 0; i < M; i++){
        cin >> a >> b;
        v[b].push_back(a);
    }
    
    int depth[10001];
    for(int i = 1; i <= N; i++){
        memset(visited, 0sizeof(visited));
        cnt = 0;
        dfs(i);
        depth[i] = cnt;
    }
    
    int max = 0;
    for(int i = 1; i <= N; i++){
        if(max < depth[i])
            max = depth[i];
    }
    
    for(int i = 0; i <= N; i++){
        if(max == depth[i])
            cout << i <<' ';
    }
        
    
    return 0;
}
 
 

'대학교 > Algorithm' 카테고리의 다른 글

[백준 9935] 문자열 폭발  (0) 2020.02.26
[백준 1717] 집합의 표현  (0) 2020.02.26
[백준 2606] 바이러스  (0) 2020.02.26
[백준 1764] 듣보잡  (0) 2020.02.24
[백준 6581] HTML  (0) 2020.02.24
Comments