[백준] 바이러스 (javascript)

https://www.acmicpc.net/problem/2606

2606번: 바이러스

 

🤔 해결방법

1. queue를 이용한 BFS
2. 처음 1번 컴퓨터를 큐에 추가하고 infected에 넣는다.
3. while 루프는 queue 배열이 비어있지 않을 때까지 반복하는데 각 반복에서 shift()를 사용해 queue 배열의 가장 앞에 있는 컴퓨터 번호를 가져오고 이것을 현재 탐색 중인 컴퓨터 current로 한다.
4. current를 infected에 추가하고 current와 연결된 컴퓨터들을 탐색하여 아직 감염되지 않은 컴퓨터면 queue에 추가 
5. 마지막으로 1번 컴퓨터를 제외한 감염된 컴퓨터의 개수를 출력

 

🔑 풀이

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

      const num = +input[0];
      const connectedComSize = +input[1];
      let lickedCom = Array.from({ length: num + 1 }, () => []);
      for (let i = 2; i < connectedComSize + 2; i++) {
        const [a, b] = input[i].split(" ").map(Number);
        connectedCom[a].push(b);
        connectedCom[b].push(a);
      }

      function solution(lickedCom) {
        let infected = new Set();
        let queue = [1];

        //queue에 남는 수가 없을 때까지
        while (queue.length > 0) {
          const current = queue.shift(); //가장 앞의 수를 삭제하고 current에 넣기
          infected.add(current); //감염

          for (let i = 0; i < connectedCom[current].length; i++) {
            //감연된 current의 옆에 있는 컴퓨터들
            const next = connectedCom[current][i];
            if (!infected.has(next)) {
              queue.push(next);
            }
          }
        }

        console.log(infected.size - 1); // 1번 컴퓨터 제외
      }

      solution(connectedCom);

 

 

😭 삽질

처음에 생각한 풀이는 다음과 같았다.

1. for문을 통해 각 배열에 1이 있으면 1을 제외한 수를 infected에 추가시킨다.

2. infected에 있는 수가 각 배열에 있으면 그 수를 제외한 수를 infected에 추가시키고 중복을 제거한다.

function solution(num, ssang, connectedCom) {
        let infected = [];

        //1과 연결된 컴퓨터 찾기
        for (let i = 0; i < connectedCom.length; i++) {
          //1과 연결되어 있다면
          if (connectedCom[i].includes(1)) {
            for (let j = 0; j < connectedCom[i].length; j++) {
              //1과 연결된 숫자 추가 (1제외)
              if (connectedCom[i][j] !== 1) {
                infected.push(connectedCom[i][j]);
              }
            }
          }
        }

        //1과 연결된 컴퓨터와 연결된 컴퓨터 찾기
        let newInfected = [];
        infected.forEach((e) => {
          for (let i = 0; i < connectedCom.length; i++) {
            if (connectedCom[i].includes(e)) {
              for (let j = 0; j < connectedCom[i].length; j++) {
                if (connectedCom[i][j] !== e && connectedCom[i][j] !== 1) {
                  newInfected.push(connectedCom[i][j]);
                }
              }
            }
          }
        });

        infected.push(...newInfected);
        infected = [...new Set(infected)];
        return infected.length;
      }

이중 for문에 이중 if문까지 정말 비효율적인 코드임은 알지만 그래도 vscode에서는 정답을 출력했다.

그런데 이를 백준에 제출하려니 문제가 생겼다.

예전에 파이썬으로 풀 때는 몰랐는데 js로 풀려고 보니까 백준에서 js는 지원하지 않아 node.js로 설정하고 제출해야 하며 index.txt 파일에 input값을 넣고 fs를 이용해 받아오고 또 내가 원하는 형태로 만들어 변수에 저장해야 했다.

한 줄로 입력받느냐 여러 줄로 입력받느냐 등에 따라서도 코드가 조금씩 달라져야 했다.

문제 자체 푸는건 오래걸리지 않았는데 백준 제출용으로 바꾸는데서 오류가 났다.

 

특히 connectedCom에 들어갈 각 배열을 받아오면 const [a, b] = input[i].split(" ").map(Number); 

나는 push를 통해 그 배열을 바로 connectedCom에 넣었다. connectedCom.push([a,b]);

그런데 오류가 났다.

검색해보니 나는 connectedCom배열의 각 요소에 [a, b] 형태로 컴퓨터 연결 정보를 저장하려고 하고 있지만

문제에서 주어진 입력 형식은 "네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수"와 "한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍"이기에 다음과 같이 입력해야 한다는데 아직도 이 부분이 이해가 잘 가지 않는다.😭

connectedCom[a].push(b);

connectedCom[b].push(a);

 

아무튼 백준 제출용으로 코드를 바꿨고 vscode에서는 정상적으로 답이 나왔는데 백준에서는 틀렸다고 나왔다.

아마 다른 히든케이스를 해결하지 못한 것 같다.😭

const fs = require("fs");
      // const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
      let input = fs
        .readFileSync(__dirname + "/input.txt")
        .toString()
        .split("\n");
      const num = parseInt(input[0]);
      const ssang = parseInt(input[1]);
      const connectedCom = Array.from({ length: num + 1 }, () => []);
      for (let i = 2; i < ssang + 2; i++) {
        const [a, b] = input[i].split(" ").map(Number);
        connectedCom[a].push(b);
        connectedCom[b].push(a);
      }

      function solution(connectedCom) {
        let infected = []; //감염

        //1과 연결된 컴퓨터 찾기
        for (let i = 0; i < connectedCom.length; i++) {
          //배열에 1이 들어있는 경우
          if (connectedCom[i].includes(1)) {
            for (let j = 0; j < connectedCom[i].length; j++) {
              //1이 아니면 감염
              if (connectedCom[i][j] !== 1) {
                infected.push(connectedCom[i][j]);
              }
            }
          }
        }

        //1과 연결된 컴퓨터와 연결된 컴퓨터 찾기
        let newInfected = [];
        infected.forEach((e) => {
          for (let i = 0; i < connectedCom.length; i++) {
            //배열에 그 컴퓨터가 들어있는 경우
            if (connectedCom[i].includes(e)) {
              for (let j = 0; j < connectedCom[i].length; j++) {
                //그 컴퓨터가 아니고 1도 아니면 감염
                if (connectedCom[i][j] !== e && connectedCom[i][j] !== 1) {
                  newInfected.push(connectedCom[i][j]);
                }
              }
            }
          }
        });

        infected.push(...newInfected);
        infected = [...new Set(infected)];
        console.log(infected.length);
      }

      solution(connectedCom);