BOJ_1325 효율적인 해킹

• TOC {:toc}

이 글은 백준 온라인 저지의 1325번 문제를 풀이한 것을 모아놓은 글입니다.

일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.

2021.07.03 (Python)

import sys
input = sys.stdin.readline

def dfs(root):
    visited = [False] * (N + 1)
    stack = [root]
    count = 0

    while stack:
        n = stack.pop()
        if not visited[n]:
            visited[n] = True
            count += 1
            stack += hack[n]

    return count

N, M = map(int, input().split())
hack = [[] for _ in range(N + 1)]

for _ in range(M):
    A, B = map(int, input().split())
    hack[B].append(A)

max_count = -1
res = []

for i in range(1, N + 1):
    c = dfs(i)
    if c > max_count:
        max_count = c
        res = [i]
    elif c == max_count:
        res.append(i)

print(*res)

아이디어 & 풀이

Python으로 풀 경우 대부분 시간 초과가 나는 것 같다. Pypy3 로 푸는 것을 권장한다.

일반적인 dfs, bfs 문제와 다른 점은 인접 노드가 단방향으로 연결되어있다는 점이다.

• A가 B를 신뢰할 때 B만이 B에서 A로 접근할 수 있다.
• 노드 사이의 연결 관계를 나타내는 hack 리스트를 구성할 때 B의 리스트에만 A가 포함되도록 해야 한다.

N개의 노드를 순회하면서 그 노드에 연결된 다른 노드의 수를 구한다.

• 각 노드를 루트로 bfs나 dfs로 탐색하고 탐색 과정에서 노드를 방문할 때마다 count를 증가시킨 뒤 count를 반환한다.
• count의 최댓값과 같은 값을 갖는 노드 번호를 res에 추가한 뒤 출력한다.
  • 노드를 오름차순으로 탐색하므로 별도로 정렬은 하지 않아도 된다.

디버그

• dfs의 인자로 visited를 전달해 사용하면 해당 대상을 그대로 보낸 거라 함수 안에서 수정을 하면 전달한 visited 자체가 수정된다.
  • dfs를 수행할 때마다 새로운 visited가 필요하기 때문에 dfs 안에서 visited를 초기화해 생성한다.

미해결

모든 노드에 대해 그래프를 매번 탐색하는 게 시간이 오래 걸릴 것 같아 어떤 컴퓨터도 신뢰하지 않는 컴퓨터만 순회하도록 작성했었는데 틀렸다.

• 자신(e.g., A)이 어떤 컴퓨터(e.g., B를 신뢰하고 있으면 B가 A보다 더 많은 컴퓨터를 해결할 수 있다고 생각했다.
• trusted 리스트를 모두 False로 초기화한 뒤 A, B를 입력받을 때마다 trusted[A] = True로 변경한 뒤
• not trusted[i]인 경우에만 dfs(i)를 실행했다.
• not trusted[i] 조건만 없애면 정답으로 처리되는 걸 보니 답으로 들어가야 할 경우를 걸러내는 것 같은데 생각해 봐야겠다.

각 노드에서 그래프를 탐색할 때, 반복적으로 거치는 부분들이 많아서 해킹할 수 있는 컴퓨터 수를 각 노드를 거칠 때마다 count에 저장해서 사용하는 방식으로 바꿔보려 했었는데 메모리 초과가 나서 하지 못했다.

• 해당 컴퓨터를 신뢰하는 다른 컴퓨터가 없으면 count 값은 1이다.
• 이미 count 값이 존재하면 그 값을 사용한다.
• 신뢰받는 컴퓨터가 있으면 그 컴퓨터들의 count 합에 자기 자신인 1을 더한다.
• count의 최댓값을 구하고 그 값을 갖는 원소를 정렬해서 출력한다.

import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def dfs(n):
    if not trusted[n]:
        count[n] = 1
        return 1
    elif count[n]:
        return count[n]
    else:
        count[n] = sum([dfs(x) for x in trusted[n]]) + 1
        return count[n]

N, M = map(int, input().split())
trusted = [[] for _ in range(N + 1)]
count = [0] * (N + 1)
res = []

for _ in range(M):
    A, B = map(int, input().split())
    trusted[B].append(A)

for i in range(1, N + 1):
    if not count[i]:
        dfs(i)

max_count = max(count)
print(*sorted([i for i, x in enumerate(count) if x == max_count]))

시간이 굉장히 짧게 걸린 풀이들이 있는데 그거 보고 파악해보기.

2022.04.05 (JS)

const fs = require("fs");
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");

function dfs(i) {
    let count = 0;

    const visited = Array(N + 1).fill(false);
    const stack = [i];
    visited[i] = true;

    while (stack.length >= 1) {
        const n = stack.pop();
        const len = edges[n].length;

        for (let i = 0; i < len; i += 1) {
            const m = edges[n][i];
            if (!visited[m]) {
                count += 1;
                visited[m] = true;
                stack.push(m);
            }
        }
    }

    hacked[i] = count;
}

const [NM, ...lines] = input;
const [N, M] = NM.split(" ").map((n) => parseInt(n));

const edges = Array(N + 1)
    .fill()
    .map((i) => []);
const hacked = Array(N + 1).fill(0);
const res = [];

lines.forEach((line) => {
    const [A, B] = line.split(" ").map((n) => parseInt(n));
    edges[B].push(A);
});

for (let i = 1; i <= N; i++) {
    dfs(i);
}

const max = Math.max(...hacked);
for (let i = 0; i <= N; i++) {
    if (hacked[i] === max) res.push(i);
}

console.log(...res);

디버그

• 시간초과가 나길래 통과한 답들이랑 비교해봤는데 가장 크게 영향을 미친것은 dfs 내에서 for문 대신에 forEach를 사용해서 순회한 것이었다. 그것만 바꿨을 때 통과하던 코드가 시간초과로 통과하지 못함.
• 그 외의 것은 시간에 영향이 있긴 했지만 크지 않았다.
  • 입력을 받을 때 for문 대신 forEach를 사용
  • 결과 문자열을 생성할 때 hacked를 순회하면서 res를 문자열로 잇는 대신 res를 배열로 해서 원소를 push 한 다음에 spread 문법을 이용해서 출력
  • dfs 함수 내에서 hacked 값을 count로 바로 지정하는 대신 count 값을 반환해서 함수 밖에서 hacked 값을 지정하는 등