[백준 1707 - Node.js] 이분 그래프

🔗 문제 링크

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

1707번: 이분 그래프

✏️ 풀이

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const K = +input.shift();
const SET_A = 1;
const SET_B = 2;

const dfs = (start, graph, visited) => {
  visited[start] = SET_A;
  const stack = [start];
  while (stack.length) {
    const node = stack.pop();
    const curSet = visited[node];
    const nextSet = curSet === SET_A ? SET_B : SET_A;
    if (!graph[node]) {
      continue;
    }
    for (let i = 0; i < graph[node].length; i++) {
      const adjNode = graph[node][i];
      if (visited[adjNode] === curSet) {
        return false;
      }
      if (!visited[adjNode]) {
        visited[adjNode] = nextSet;
        stack.push(adjNode);
      }
    }
  }
  return true;
};

const output = Array(K).fill('YES');

for (let i = 0; i < K; i++) {
  const [V, E] = input.shift().split(' ').map(Number);
  const edges = input.splice(0, E).map(v => v.split(' ').map(Number));
  const graph = edges.reduce((acc, v) => {
    const from = v[0];
    const to = v[1];
    if (acc[from]) {
      acc[from].push(to);
    } else {
      acc[from] = [to];
    }
    if (acc[to]) {
      acc[to].push(from);
    } else {
      acc[to] = [from];
    }
    return acc;
  }, {});
  
  const visited = Array(V + 1).fill(0);
  for (let j = 1; j <= V; j++) {
    if (visited[j]) {
      continue;
    }
    if (!dfs(j, graph, visited)) {
      output[i] = 'NO';
      break;
    }
  }
}

console.log(output.join('\n'));

일단 output에 'YES'를 테스트 케이스의 개수만큼 담아서 초기화한다. 일단 모든 테스트 케이스의 그래프가 이분 그래프일 것이라고 가정한 것이다.

 

DFS를 하면서 현재 노드와 인접 노드들을 서로 다른 집합으로 분류시킨다. 만약 인접 노드들 중에 현재 노드와 동일한 집합에 이미 속해 있는 경우 즉시 이분 그래프가 아님을 알 수 있다.

 

DFS를 할 때 시작 노드를 SET_A로 설정하고, 인접 노드들을 SET_B로 설정한다. 만약 현재 노드가 SET_B이면 인접 노드들은 SET_A로 설정한다. SET_A, SET_B 여부는 별도로 stack에 같이 넣지 않고 visited에 저장하였다.

 

DFS를 계속 진행하다가 현재 노드의 인접 노드들 중에서 현재 노드와 동일한 집합에 이미 속해 있는 노드가 존재하면 그 즉시 false를 반환하여 현재 그래프가 이분 그래프가 아님을 판단하여 output[i]를 'NO'로 갱신한다.

 

마지막으로 모든 테스트 케이스에 대해 output을 갱신한 결과를 개행 문자로 이어 붙여 출력하였다.