백준 2606(바이러스) - Node.js

DFS(깊이우선탐색)가 너무 머리에 안 들어오다가 같은 문제를 계속 보다보니까 이제 뭔가 "아하!" 하는게 생겼다.

아래는 백준 2606 바이러스 문제이다.

물론 백준에서 직접 readFileSync해서 파일 불러오는 것부터 해보면 좋지만 나는 목적이 문제 해결 능력이다보니 겉치레는 치우고, 콘솔을 찍어볼 수 있도록 주로 JDoodle 같은 곳에서 문제를 풀어보는 편이다.

그럼 문제를 살펴보자.

 

백준2606(바이러스)

 

백준 2606 예제 입력, 출력

 

위 예제 입력을 보다시피 input은 아래와 같이 사용한다.

const input = [
    7,
    6,
    1 2,
    2 3,
    1 5,
    5 2,
    5 6,
    4 7
]

 

그리고 문제를 풀어보자. 전체 해결 코드는 아래와 같다.

function solution(input) {
    let answer = 0;
    
    const N = Number(input[0]);
    const M = Number(input[1]);
    const connections = input.slice(2).map(line => line.split(' ').map(Number));

    const graph = Array.from({length: N + 1}, () => []);
    
    connections.forEach(([a, b]) => {
        graph[a].push(b);
        graph[b].push(a);
    })
    
    const visited = Array.from(Array(N + 1), () => 0);
    
    function dfs(v) {
        visited[v] = 1;
        graph[v].forEach(next => {
            if(!visited[next]) dfs(next);
        })
    }
    
    dfs(1);
    
    answer = visited.filter(v => v).length - 1
    
    return answer;
}

console.log(solution(input)) // 4

 

---

 

이제 문제 풀이를 해보자.

우선 input 값을 보면 아래와 같다.

const input = [
  '7',      // 컴퓨터 수
  '6',      // 연결 수
  '1 2',    // 연결 정보 
  '2 3',
  '1 5',
  '5 2',
  '5 6',
  '4 7'
]

 

input 값에 모든 값이 다 들어오기 때문에 나눠야한다.

N은 "컴퓨터 수", M은 "연결 수", connections는 "연결정보" 를 뜻한다.

 

그 다음 그래프를 인접 리스트 형식으로 초기화 시킨다.

const graph = Array.from({length: N + 1}, () => []);
// [ [], [], [], [], [], [], [], [] ]

 

그리고 방문 배열을 초기화 시키자 boolean으로 해도 좋고, 0과 1 또한 boolean으로 사용할 수 있으니 무방하다.

const visited = Array.from(Array(N + 1), () => 0);
// [ 0, 0, 0, 0, 0, 0, 0, 0 ]

 

이제 DFS를 사용할건데 1번부터 DFS 함수에 들어가서 시작하게 된다.

DFS 함수 안에서는 어떤 일이 벌어지는지 보자.

function dfs(v) {
    visited[v] = 1; // 현재 노드를 방문 표시
    
    graph[v].forEach(next => {
        if(!visited[next]) dfs(next); // 방문하지 않은 노드에 대해 재귀 호출
    });
}

 

그리고 마지막으로 visited라는 방문 배열에서 방문한 컴퓨터의 수를 세고, 1번 컴퓨터를 제외한 수를 answer에 넣고 return 시키면 마무리가 된다.