백준 1119번 그래프 (Node.js)

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

1119번: 그래프

 

 

 

문제풀이

 

문제를 제일 처음 봤을 때, 생각나는 구조는 트리구조 였습니다.

점이 N개 주어졌을 때,  그래프에서 각각의 점들이 연결된 선 (간선)이 N-1 개라면 변형에 의해서 각각의 떨어진 점 들을 교환을 통해서 이을 수 있습니다.

 

1 .따라서 우선적으로는 간선의 개수와 정점의 개수를 먼저 확인합니다.

(만약 5개의 점인데 선이 3개라면 이을 수 없으니깐요..) 

 

const fs = require('fs');
const input = fs
  .readFileSync(__dirname + '/input.txt')
  .toString()
  .split('\n');

const n = +input[0];
let edge = 0;
const graph = Array.from(Array(n), () => []);

for (let i = 1; i <= n; i++) {
  const nodes = input[i].split('');
  for (let j = 0; j < n; j++) {
    if (nodes[j] === 'Y') {
    // 양방향 그래프이므로, 간선의 개수를 셀 때 0.5를 더 해줌
      edge += 0.5;
      graph[i - 1].push(j);
    }
  }
}

입력 값을 받고 ,  이를 그래프에 등록하면서 간선의 개수를 측정합니다.

 

이후 간선의 개수가 작다면 -1을 출력합니다.

 

if (edge < n - 1) return console.log(-1);

 

 

이후 주어진 그래프에서 서로 연결된 컴퍼넌트(덩어리)가 몇 개인지 측정해줍니다.

이때 사용한 것이 DFS 알고리즘입니다.

const visited = Array(n).fill(false);
let comp = 0;

for (let i = 0; i < n; i++) {
  if (!visited[i]) {
    comp++;
    dfs(i);
  }
}

function dfs(index) {
  visited[index] = true;
  for (let i = 0; i < graph[index].length; i++) {
    !visited[graph[index][i]] && dfs(graph[index][i]);
  }
}

console.log(comp - 1);

 

방문 처리를 통해서 이미 방문한 지점은 추가 방문을 방지하고, dfs알고리즘에 대해서 하나의 점에 대한 탐색을 끝냈음에도 방문이 되지 않은 점이 있다면, 이는 다른 컴퍼넌트입니다. 따라서 이때 comp++을 실행해줍니다.

 

앞에서 이미 간선이 부족해서 수정이 되지 않는 경우에 대한 처리를 했기 때문에,  서로 떨어진 컴퍼넌트를 연결만 하면 됩니다.  따라서 comp-1 개를 출력합니다.

 

하지만 문제 조건 중에서, 이미 연결된 선들을 분해 한 후에, 4개의 점에 대한 연결을 진행합니다. 따라서  아무것도 연결되지 않은 점은 연결할 수 없습니다. ( 다만 정점이 하나인 경우는 예외처리해야합니다.)

이를 반영한 최종 코드는

 

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

const n = +input[0];
let edge = 0;
const graph = Array.from(Array(n), () => []);
const visited = Array(n).fill(false);

for (let i = 1; i <= n; i++) {
  const nodes = input[i].split('');
  for (let j = 0; j < n; j++) {
    if (nodes[j] === 'Y') {
      edge += 0.5;
      graph[i - 1].push(j);
    }
  }
}

if (edge < n - 1) return console.log(-1);
// 아무것도 연결되지 않은 점이 있다면
for (let i = 0; i < n; i++) {
  if (graph[i].length === 0 && n !== 1) return console.log(-1);
}
let comp = 0;

for (let i = 0; i < n; i++) {
  if (!visited[i]) {
    comp++;
    dfs(i);
  }
}

function dfs(index) {
  visited[index] = true;
  for (let i = 0; i < graph[index].length; i++) {
    !visited[graph[index][i]] && dfs(graph[index][i]);
  }
}

console.log(comp - 1);