BOJ 1325 · 효율적인 해킹

알고리즘 분류 : BFS  

BFS를 통해 모든 노드를 탐색하고, 탐색 가능한 최댓값을 구하는 문제다.

A가 B를 신뢰할 경우, B를 해킹하면 A도 해킹이 가능하다. A가 B를 신뢰한다는 것을 다르게 말하면, B → A 로 연결된 방향 그래프라고 말할 수 있다.

• 입력받으면서 A와 B의 신뢰 관계를 연결 리스트로 저장한다.
• 컴퓨터 개수가 N개일 때, 1부터 N까지 BFS를 N번 호출하여 해킹 가능한 최대 컴퓨터 개수를 저장한다.
• 이때 가장 많이 해킹할 수 있는 컴퓨터의 번호를 답으로 출력한다.
• 답이 여러 개일 수 있으므로, 컴퓨터 번호를 별도의 리스트에 저장한다.

---

C++ 소스코드

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

int n, m;
vector<int> a[10001];
vector<int> ans;
bool check[10001];
int hacking = 0;

void bfs(int i) {
    queue<int> q;
    q.push(i);
    check[i] = true;
    int cnt = 0;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (auto k : a[x]) {
            if (check[k]) continue;
            q.push(k);
            check[k] = true;
            cnt++;
        }
    }
    if (hacking < cnt) {
        hacking = cnt;
        ans.clear();
        ans.push_back(i);
    } else if (hacking == cnt) {
        ans.push_back(i);
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i=0; i<m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        a[v].push_back(u);
    }
    for (int i=1; i<=n; i++) {
        memset(check, false, sizeof(check));
        bfs(i);
    }
    sort(ans.begin(), ans.end());
    for (auto k : ans) printf("%d ", k);
    printf("\n");
    return 0;
}

✓ 범위 기반 for문(Ranged based for loop)과 auto 변수를 사용했다. 이 기능은 C++ 11 이상에서 지원한다.

---

PyPy3 소스코드

from collections import deque
from sys import stdin
input = stdin.readline

n, m = map(int, input().split())
a = [[] for _ in range(n+1)]
check = [False for _ in range(n+1)]
ans = []
hacking = 0

def bfs(i):
    global hacking
    q = deque()
    q.append(i)
    check[i] = True
    cnt = 0
    while q:
        x = q.popleft()
        for k in a[x]:
            if check[k] is False:
                q.append(k)
                check[k] = True
                cnt += 1
    if hacking < cnt:
        hacking = cnt
        ans.clear()
        ans.append(i)
    elif hacking == cnt:
        ans.append(i)

for _ in range(m):
    u, v = map(int, input().split())
    a[v].append(u)
for i in range(1, n+1):
    check = [False for _ in range(n+1)]
    bfs(i)
ans.sort()
for i in ans:
    print(i, end=' ')
print()

✓ Python 3로 제출하면 시간 초과가 나오므로 PyPy3로 제출해야 한다.

---

참고

• 백준 온라인 저지 : BOJ 1325