[백준 node.js] 11724번_연결 요소의 개수

백준 DFS 알고리즘 11724번_연결 요소의 개수

난이도 : 실버II

 

문제 설명

입출력

 

문제 풀이 : 이 문제 또한 전형적인 DFS 문제이다. 또한 문제 제목처럼 연결된 정점들의 묶음의 수를 출력하면된다.

기존에는 한번만 DFS함수를 호출하면 재귀적으로 돌면서 인접 노드들을 알아낼 수 있다.

그렇게 되면 한번의 호출만으로 i(시작노드)와 인접한 모든 노드들은 방문 처리가 된다.

이를 이용하여 반복문을 통해서 graph의 길이만큼 DFS함수를 호출한다. 하지만 처리된 노드들은 방문처리가 되었기 때문에 방문되지않은 노드가 있을때만 DFS함수를 호출하고 연결요소를 카운트 해주면된다.

 

//실버2 연결 요소의 개수

//DFS 기본 로직과 동일
function DFS(v) {
  visited[v] = true;
  for (let i = 1; i < graph.length; i++) {
    if (graph[v][i] === 1 && visited[i] === false) {
      DFS(i);
    }
  }
}

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 () {
  let [n, m] = input[0].split(" ").map((el) => parseInt(el));
  input = input.slice(1);
  //그래프 정점 개수만큼 초기화
  graph = Array.from(Array(n + 1), () => Array(n + 1).fill(0));
  //방문표시를 위한 visited도 초기화
  visited = new Array(n + 1).fill(false);

  //연결 간선의 정보를 좌표로 그래프에 넣어준다.
  for (let i of input) {
    let [x, y] = i.split(" ").map((el) => parseInt(el));
    graph[x][y] = 1;
    graph[y][x] = 1;
  }

  //연결 요소 개수 카운트 변수
  let cnt = 0;
  //정점의 개수만큼 DFS실행
  for (let i = 1; i < n; i++) {
    //i의 정점에 대해 DFS를 한번 수행하고 나오면 i와 연결된 정점들은
    //전부 방문 처리가 된 상태일것이다. 따라서 반복문을 통해 모든 리스트의
    //돌면서 그 정점이 아직 처리가 안된것이라면 이전의 정점들과는 연결되지 않았음을 의미한다.
    if (visited[i] === false) {
      DFS(i);
      cnt += 1;
    }
  }
  console.log(cnt);
  process.exit();
});

* DFS알고리즘은 손댈것이 없어서 금방 풀었는데 2번째 케이스에서 6번 정점이 방문처리 되지 않고 자꾸 말썽을 부렸다.. 분명 맞게한건데 안되길래 디버깅을 통해 한줄한줄따라갔다. 이상한 곳에서 문제가 발생했다.

for문 사용할때 (let i=0;) 이런식으로 사용하는데 let 선언이 없어도 제대로 실행되길래 가끔 let 선언을 빼먹고 사용하곤했다. 그래서 i범위가 1~7사이인데 갑자기 i값이 10으로 뛰어버려 문제가 발생했었다. 그래서 let선언을 해주고 제출하니 풀었다.

아마 let선언을 안해줘서 i값이 글로벌 변수로 인식해서 재귀나 다른 i들과 꼬여서 그런 문제들이 발생한것 같다.

역시 사소한 실수도 조심해야하고 디버깅이 짱인것을 느꼈다...