[백준 node.js] 2606번_바이러스

백준 DFS알고리즘 2606번_바이러스

난이도 : 실버 III

 

문제 설명

입출력

 

문제 풀이 : 이 문제는 DFS 알고리즘의 대표적인 문제이다. 인접행렬을 통해 연결된 노드의 개수를 구하는 문제이다.

입력으로 주어지는 쌍을 해당 값에 맞는 인덱스에 1을 대입하여 연결된 노드가 있음을 알려준다.

그 후, 방문처리를 위해 배열을 초기화 해주고 인덱스 1부터 dfs함수를 실행시켜 dfs기능을 실행해주면된다.

자세한 설명은 코드에 주석으로 달아놨습니다.

 

재귀풀이

//실버3 바이러스
function solution(n, graph) {
  //방문노드 초기화
  visited = new Array(n + 1).fill(false);
  //노드 1로 dfs시작
  dfs(n, 1);
  //dfs의 재귀가 끝난후 로직
  let cnt = 0;
  //1번 컴퓨터를 통해 바이러스 걸리게 되는 컴퓨터수니깐 1을 제외하고 실행
  for (let i = 2; i <= n; i++) {
    if (visited[i] === true) {
      cnt += 1;
    }
  }
  console.log(cnt);
}

function dfs(n, start) {
  //현재 노드 방문처리
  visited[start] = true;

  for (let i = 1; i <= n; i++) {
    //그래프에서 현재 노드에 해당하는 인접행렬 탐색해서 연결노드가 있거나
    //그 연결된 노드가 아직 방문 처리되지 않았다면 그 노드로 재귀실행
    if (graph[start][i] === 1 && visited[i] === false) {
      dfs(n, i);
    }
  }
}

const { format } = require("path");
const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

//전역 변수로 이용
let input = [];
let graph = [];
let visited = [];

rl.on("line", function (line) {
  //여러줄 입력
  input.push(line);
}).on("close", function () {
  //es6문법 구조분해 할당후 map을 통해 형 변환
  let [n, m] = input.map((el) => parseInt(el));
  input = input.slice(2);

  // 1번 노드부터 사용하기 위해 n+1로 크기 사용
  graph = Array.from(Array(n + 1), () => Array(n + 1).fill(0));

  for (let i of input) {
    //구조분해 할당으로 x,y에 입력 쌍 대입
    let [x, y] = i.split(" ").map((el) => parseInt(el));
    //x,y는 x,y에서 서로 갈 수 있다는 의미이므로 양방향 그래프에 1대입
    //양방향인 이유는 연결쌍이  5,1  5,3으로 주어지면 1의 연결노드는 3,5인데
    //단방향으로 하게되면 1에서 연결된것이 없으므로 인접노드가 없다고 뜬다
    graph[x][y] = 1;
    graph[y][x] = 1;
  }
  
  solution(n, graph);
  process.exit();
});

 

반목문풀이

function solution(n, graph) {
  //방문노드 초기화
  visited = new Array(n + 1).fill(false);
  let result = 0;
  //노드 1로 dfs시작
  result = dfs(n, 1);
  console.log(result);
}

function dfs(n, start) {
  //현재 노드 방문처리
  visited[start] = true;
  let stack = [];
  let cnt = 0;
  //시작노드 삽입
  stack.push(start);
  while (stack.length !== 0) {
    let tmp = stack.pop(); //연결된 인접노드 가져옴
    for (let i = 1; i <= n; i++) {
      //현재 노드와 연결된것이 있고 그 연결노드가 아직 미방문이면
      if (graph[tmp][i] === 1 && visited[i] === false) {
        stack.push(i); //인접노드 삽입
        cnt += 1; // 감염수
        visited[i] = true; //인접노드 방문처리
      }
    }
  }
  return cnt;
}

 

* 평소 유튜브를 통해 개발에 관련된 영상을 많이 보는데 유익한 정보를 얻어 사용해봤다.

es6문법을 어느정도 알고 사용하고있었고 구조분해 문법도 알고 있었지만, 정작 사용하지않고 있었다.

구조분해 문법을 통해 n,m과 같은 입력값을 한번에 처리할 수 있어서 더욱 편리했다 ㅎㅎ..(js문법의 세계는 무궁무진한것 같다...)

 

그리디 문제를 어느정도 풀고나서  DFS의 기본적인 원리만 익히고 바로 문제풀이에 들어갔다.

비교적 쉬운 난이도를 선택해서 풀었지만 배운 개념을 실제로 적용하기엔 너무나 힘들었다. 막무가내로 풀면서 남들 코드를 보았는데도 이해가 안 됐다. 왜 양방향으로 값을 넣어야만하는지 한개만 주어지는 테스트 케이스로는 파악하기 힘들었다. 그래서 다시 DFS를 찾아보고 공부하기 시작했다. 제대로 익히고 나니 원리와 풀이 과정이 이해되었고 어떻게 접근하고 풀어야하는지 그제서야 눈에 들어왔다.

이론부터 제대로 익히고 문제를 풀어야겠다는 생각이 들었다 ㅠㅠ

 

수정) 반복문으로 해결한 풀이도 추가해뒀습니다!