[백준] JavaScript - 효율적인 해킹 (1325)

개요

문제 이름: 효율적인 해킹 (1325)
문제 링크: https://www.acmicpc.net/problem/1325
플랫폼: 백준
알고리즘 분류: DFS
소요 시간: 1시간 30분

 

문제 전문

설명

입출력

 

문제 풀이

해설

이 문제는 N개의 컴퓨터로 구성된 네트워크에서 가장 효율적으로 해킹할 수 있는 컴퓨터를 찾는 문제입니다. 네트워크의 특징은 신뢰 관계를 기반으로 하며, A 컴퓨터가 B 컴퓨터를 신뢰하는 경우 B 컴퓨터를 해킹하면 A 컴퓨터도 자동으로 해킹할 수 있다는 점입니다.

 

문제를 해결하기 위해 DFS(깊이 우선 탐색) 알고리즘을 사용합니다. DFS는 한 정점에서 시작하여 가능한 한 깊이 들어가면서 연결된 모든 정점을 방문하는 알고리즘으로, 이 문제에서는 각 컴퓨터에서 시작하여 해킹할 수 있는 모든 컴퓨터를 찾는 데 사용됩니다.

 

우선 입력으로 주어지는 정보는 다음과 같습니다.

• 첫째 줄에는 컴퓨터의 개수 N(1 ≤ N ≤ 10,000)과 신뢰 관계의 개수 M(1 ≤ M ≤ 100,000)이 주어집니다.
• 이어서 M개의 줄에 걸쳐 두 정수 A와 B가 주어지며, 이는 A가 B를 신뢰한다는 의미입니다.
• 각 컴퓨터는 1번부터 N번까지 번호가 매겨져 있습니다.

이 문제를 해결하기 위한 접근 방식은 다음과 같습니다.

1. 신뢰 관계를 방향 그래프로 표현합니다.
   • B를 해킹하면 A도 해킹할 수 있으므로, A -> B가 아닌 B -> A 방향으로 간선을 저장합니다.
   • 인접 리스트를 사용하여 그래프를 구현합니다.
2. 각 컴퓨터를 시작점으로 하여 DFS를 수행합니다.
   • DFS를 통해 현재 컴퓨터에서 해킹할 수 있는 모든 컴퓨터를 찾습니다.
   • visited 배열을 사용하여 이미 방문한 컴퓨터를 체크합니다.
   • 방문할 때마다 카운터를 증가시켜 해킹 가능한 컴퓨터의 수를 계산합니다.
3. 최대 해킹 가능 컴퓨터 수를 갱신하며 결과를 저장합니다.
   • 현재까지의 최대값보다 큰 값을 찾으면 결과 배열을 초기화하고 현재 컴퓨터 번호를 저장합니다.
   • 최대값과 같은 값을 찾으면 현재 컴퓨터 번호를 결과 배열에 추가합니다.
4. 결과를 오름차순으로 정렬하여 출력합니다.
   • 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터들의 번호를 공백으로 구분하여 출력합니다.

이러한 방식으로 모든 컴퓨터에 대해 해킹 가능한 컴퓨터의 수를 계산하고, 그 중 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터들을 찾아낼 수 있습니다.

 

시도

1차 시도 (실패)

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const [N, M] = input[0].split(' ').map(Number);
const graph = Array.from({ length: N + 1 }, () => []);

// 신뢰 관계 그래프 생성 (반대 방향으로)
for (let i = 1; i <= M; i++) {
    const [a, b] = input[i].split(' ').map(Number);
    graph[b].push(a);
}

function bfs(start) {
    const visited = new Array(N + 1).fill(false);
    const queue = [start];
    let count = 1;
    visited[start] = true;

    while (queue.length > 0) {
        const current = queue.shift();
        for (const next of graph[current]) {
            if (!visited[next]) {
                visited[next] = true;
                queue.push(next);
                count++;
            }
        }
    }
    return count;
}

// 각 컴퓨터별로 해킹 가능한 컴퓨터 수 계산
const result = [];
let maxCount = 0;

for (let i = 1; i <= N; i++) {
    const count = bfs(i);
    if (count > maxCount) {
        maxCount = count;
        result.length = 0;
        result.push(i);
    } else if (count === maxCount) {
        result.push(i);
    }
}

console.log(result.join(' '));

이 코드는 BFS를 사용하여 각 정점에서 시작하여 해킹할 수 있는 컴퓨터의 수를 계산하고, 최댓값을 갱신하면서 결과 배열에 정점을 추가합니다.

 

그러나 이 코드는 시간 초과로 인해 문제를 통과하지 못합니다. 시간 초과가 발생한 이유는 다음과 같습니다.

1. 입력 처리 과정에서의 비효율성
   1. 코드에서는 입력값을 한 줄씩 읽어와 split() 및 map()을 사용하여 숫자로 변환하는 작업을 수행합니다.
   2. 이 과정에서 불필요한 연산 시간이 소모됩니다.
   3. 입력값의 크기가 크지 않다면 큰 문제가 되지 않을 수 있지만, 입력값의 크기가 커질수록 이 부분에서 시간 초과가 발생할 가능성이 높아집니다.
2. BFS 구현에서의 비효율성
   1. BFS 함수 내에서 shift() 연산을 사용하여 큐에서 요소를 제거합니다.
   2. shift() 연산은 배열의 첫 번째 요소를 제거하고 나머지 요소들을 앞으로 이동시키는 작업을 수행합니다.
   3. 이 연산은 배열의 크기에 비례하는 시간 복잡도를 가지므로, 큐의 크기가 커질수록 성능에 부정적인 영향을 미칩니다.
   4. 큐의 크기가 N이 될 수 있으므로, 최악의 경우 O(N^2)의 시간 복잡도를 가질 수 있습니다.
3. 그래프 탐색 과정에서의 비효율성
   1. BFS 함수 내에서 for...of 루프를 사용하여 그래프의 인접 리스트를 순회합니다.
   2. for...of 루프는 배열의 요소를 하나씩 순회하면서 요소를 가져오는 작업을 수행합니다.
   3. 이 루프는 일반적인 for 루프에 비해 느린 성능을 보입니다.
   4. 그래프의 인접 리스트를 순회할 때마다 for...of 루프를 사용하면 불필요한 부하가 발생합니다.

위와 같은 비효율적인 부분들이 누적되어 전체적인 실행 시간이 증가하게 되고, 결과적으로 시간 초과로 이어지게 됩니다.

 

특히, 입력값의 크기가 커질수록 이러한 비효율성의 영향이 더욱 크게 나타나게 되는데요. 문제에서 주어진 조건에 따르면 정점의 개수 N은 최대 10,000이고 간선의 개수 M은 최대 100,000입니다. 이는 그래프의 크기가 상당히 크다는 것을 의미하며, 비효율적인 코드로는 시간 제한 내에 문제를 해결이 불가능하게 됩니다. 물론 다른 일부 언어라면 넘어갈 여지가 있겠지만 자바스크립트에서는 적어도 아닙니다.

 

이러한 요인들로 인해 코드의 실행 시간이 늘어나고 시간 초과가 발생하게 됩니다. 따라서 2차 시도에서는 시간 초과 관련한 개선을 시도했습니다.

 

2차 시도 (성공)

// 입력을 한 번에 처리: split('\n') 후 바로 숫자 배열로 변환
// 이렇게 하면 이후 추가 형변환이 필요없어 성능상 이점이 있음
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n').map(v => v.split(' ').map(Number));
const [N, M] = input[0];

// 인접 리스트 생성
// 각 컴퓨터별로 해킹할 수 있는 컴퓨터들의 목록을 저장
const graph = Array.from({ length: N + 1 }, () => []);

// 신뢰 관계 입력
// input[i]는 이미 숫자 배열이므로 추가 변환 없이 바로 사용 가능
for (let i = 1; i <= M; i++) {
    const [a, b] = input[i];
    graph[b].push(a); // b를 해킹하면 a도 해킹할 수 있음
}

// DFS로 해킹 가능한 컴퓨터 수를 계산하는 함수
function dfs(start) {
    const stack = [start];
    const visited = new Array(N + 1).fill(false);
    let count = 1; // 시작 컴퓨터도 포함하므로 1부터 시작
    visited[start] = true;
    
    while (stack.length > 0) {
        const current = stack.pop();
        
        // 일반적인 for loop 사용: 배열 길이에 직접 접근하는 것이
        // for...of나 forEach보다 더 빠를 수 있음
        for (let i = 0; i < graph[current].length; i++) {
            const next = graph[current][i];
            if (!visited[next]) {
                visited[next] = true;
                stack.push(next);
                count++;
            }
        }
    }
    
    return count;
}

// 최대 해킹 가능한 컴퓨터 수를 찾음
let maxCount = 0;
const result = [];

// 각 컴퓨터를 시작점으로 해서 해킹 가능한 컴퓨터 수를 계산
for (let i = 1; i <= N; i++) {
    const count = dfs(i);
    if (count > maxCount) {
        maxCount = count;
        result.length = 0; // 배열을 비우는 가장 빠른 방법
        result.push(i);
    } else if (count === maxCount) {
        result.push(i);
    }
}

// 결과 출력
// 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터들의 번호임
console.log(result.join(' '));

1차 시도와 마찬가지로 이 코드는 DFS 알고리즘을 사용하여 문제를 해결합니다.

 

1차 시도와 비교했을 때 차이점은 다음과 같습니다.

1. 입력 처리 과정에서 split()과 map()을 한 번에 처리하여 불필요한 연산을 줄였습니다.
2. BFS 대신 DFS를 사용하였습니다. DFS는 스택을 사용하므로 요소를 제거할 때 O(1)의 시간 복잡도를 가집니다.
3. for...of 루프 대신 일반적인 for 루프를 사용하여 그래프의 인접 리스트를 순회하였습니다. 일반 for 루프는 배열의 길이에 직접 접근하므로 for...of보다 빠릅니다.
4. 결과 배열을 비울 때 result.length = 0을 사용하여 배열을 빠르게 비웠습니다.

이러한 개선 사항들을 통해 코드의 실행 시간을 줄일 수 있었고, 시간 초과 없이 문제를 해결할 수 있었습니다.

 

각 단계별로 내용을 자세히 설명하면 다음과 같습니다.

1. 입력 데이터 처리
   1. fs 모듈을 사용하여 입력 데이터를 한 번에 읽어옵니다.
   2. toString()으로 문자열로 변환하고, trim()으로 양끝 공백을 제거합니다.
   3. split('\n')으로 줄 단위로 분리하고, 각 줄을 map()을 사용해 숫자 배열로 변환합니다.
   4. 첫 번째 줄에서 [N, M]을 구조분해할당으로 추출합니다.
2. 그래프 초기화 및 구성
   1. Array.from()을 사용하여 크기가 N+1인 인접 리스트를 생성합니다.
   2. 각 인덱스의 초기값은 빈 배열([])입니다.
   3. 1부터 M까지 반복하면서 신뢰 관계를 그래프에 추가합니다.
   4. 이때 B를 해킹하면 A도 해킹할 수 있으므로, graph[b]에 a를 추가합니다.
3. DFS 함수 구현
   1. 시작 컴퓨터 번호를 매개변수로 받는 dfs 함수를 정의합니다.
   2. visited 배열로 방문 여부를 체크하고, stack으로 DFS를 구현합니다.
   3. count 변수로 해킹 가능한 컴퓨터 수를 카운트합니다.
   4. 스택이 빌 때까지 다음을 반복합니다.
      1. 스택에서 현재 컴퓨터를 꺼냅니다(pop).
      2. 현재 컴퓨터와 연결된 모든 컴퓨터를 확인합니다.
      3. 방문하지 않은 컴퓨터는 방문 처리하고 스택에 추가합니다.
      4. 방문할 때마다 count를 증가시킵니다.
   5. 최종적으로 해킹 가능한 총 컴퓨터 수를 반환합니다.
4. 최대 해킹 가능 컴퓨터 탐색
   1. maxCount 변수로 최대 해킹 가능 컴퓨터 수를 관리합니다.
   2. result 배열에 최대 해킹이 가능한 컴퓨터들의 번호를 저장합니다.
   3. 1번부터 N번 컴퓨터까지 각각 dfs를 수행하면서...
      1. 현재 컴퓨터에서 해킹 가능한 컴퓨터 수를 계산합니다.
      2. 이 값이 maxCount보다 크면 result 배열을 초기화하고 현재 컴퓨터 번호를 저장합니다.
      3. maxCount와 같으면 result 배열에 현재 컴퓨터 번호를 추가합니다.
5. 결과 출력
   1. result 배열의 모든 요소를 공백으로 구분하여 문자열로 변환합니다.
   2. join(' ')을 사용하여 배열을 문자열로 만듭니다.
   3. console.log()로 최종 결과를 출력합니다.

사용된 주요 메서드

• Array.from(arrayLike[, mapFn[, thisArg]]): 유사 배열 객체나 반복 가능한 객체로부터 새로운 Array 인스턴스를 생성합니다.
• Array.prototype.map(callback(currentValue[, index[, array]])[, thisArg]): 배열의 모든 요소에 대해 제공된 함수를 호출한 결과를 모아 새로운 배열을 반환합니다.
• Array.prototype.fill(value[, start[, end]]): 배열의 시작 인덱스부터 끝 인덱스의 이전까지 정적인 값 하나로 채웁니다.
• Array.prototype.push(...items): 배열의 끝에 하나 이상의 요소를 추가하고, 배열의 새로운 길이를 반환합니다.
• Array.prototype.pop(): 배열에서 마지막 요소를 제거하고 그 요소를 반환합니다.
• Array.prototype.join([separator]): 배열의 모든 요소를 연결해 하나의 문자열로 만듭니다.

 

시간 복잡도와 공간 복잡도

• 시간 복잡도: O(N * (N + M))
  • 각 정점마다 DFS를 수행하므로 N * (N + M)
  • N개의 정점 각각에 대해 DFS를 수행함
  • 각 DFS에서는 모든 정점을 방문(O(N))하고 모든 간선을 탐색(O(M))
  • 따라서 각 DFS의 시간 복잡도는 O(N + M)임
  • 단, 이를 N개의 정점에 대해 수행하므로 최종 시간 복잡도는 O(N * (N + M))
  • 물론 이러한 복잡도는 최악의 경우를 가정한 것이니까... 실제로는 visited 배열로 인해 이미 방문한 정점은 다시 방문하지 않으므로 평균적으로는 이보다 빠를 수도?

• 공간 복잡도: O(N + M)
  • 그래프의 인접 리스트를 저장하는 데 O(M)의 공간이 필요합니다.
  • DFS에서 사용되는 스택과 방문 배열은 최대 O(N)의 공간을 차지합니다.
  • 따라서 전체 공간 복잡도는 O(N + M)입니다.