개발 지식/알고리즘

[백준] 1325 효율적인 해킹

트리맨스 2021. 5. 8. 00:59
반응형

 

문제를 살펴보고 오자.

www.acmicpc.net/problem/1325

 

1325번: 효율적인 해킹

첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한

www.acmicpc.net

 

문제를 읽어보면, 간단한 그래프 탐색 문제이다. A가 B를 신뢰하는 경우에 B를 해킹하면 A를 해킹할 수 있다는 말에서, 단방향 그래프 특성을 알 수 있다.

 

이를 이용해서 문제 풀이를 간단히 구상해보자. 노드의 개수(N)이 최대 만 개 이나 주어진 시간이 5초로 매우 넉넉하기 때문에, 마음에 드는 그래프 탐색 알고리즘을 하나 선택해서 구상해 보자. 나는 bfs 알고리즘을 사용했다.

 

모든 노드에 대해서 bfs를 돌린다. 임의의 시작 노드에 대하여 bfs를 돌린 결과값은 탐색한 노드의 수이다. queue에 숫자를 push 할 때 count 를 올려준다. 모든 결과에서 최댓값에 해당하는 시작 노드를 모두 출력하면 된다. 오름차순 출력이므로 간단히 구현이 가능하다.

 

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
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
 
vector<int> v[10001];
 
int bfs(int start, int N)
{
    int ans = 0;
    int visited[10001= {0};
    queue<int> q;
 
    q.push(start);
    visited[start] = 1;
    while(!q.empty())
    {
        int start = q.front();
        q.pop();
        for(auto i = v[start].begin(); i != v[start].end(); i++)
        {
            if (!visited[*i])
            {
                visited[*i] = 1;
                q.push(*i);
                ans++;
            }
        }
    }
    return (ans);
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int N, M, a, b, ans;
    int arr[10001];
 
    cin >> N >> M;
    while (M--)
    {
        cin >> a >> b;
        v[b].push_back(a);
    }
    ans = 0;
    for (int i = 1; i <= N; i++)
    {
        arr[i] = bfs(i, N);
        ans = max(ans, arr[i]);
    }
        
    for (int i = 1; i <= N; i++)
        if (ans == arr[i])
            cout << i << " ";
    return (0);
}
cs

 

평범한 bfs를 사용했다. 코드를 줄일 수 있는 방법이 있으면 조금 더 찾아봐야 할 듯 하다.

 

반응형

'개발 지식 > 알고리즘' 카테고리의 다른 글

[백준] 2661 좋은 수열  (0) 2021.05.14
[백준] 1058 친구  (0) 2021.05.08
[백준] 1074 Z  (0) 2021.04.30
[백준] 2638 치즈  (0) 2021.04.24
[백준] 2636 치즈  (0) 2021.04.24