[JS][백준]16168_퍼레이드

문제 번호

16168번: 퍼레이드

 

 

 

알고리즘 분류

• 그래프 이론
• 자료 구조
• 그래프 탐색
• 분리 집합
• 오일러 경로

 

문제 풀이

 오일러 경로 알고리즘을 이용했다. 

모든 간선을 지나야 하고 정점은 2회 이상 지나도 상관없기 때문이다. 오일러 경로를 만족하려면 '연결 그래프'여야 하고 차수가 홀수인 정점이 0개 혹은 2개 여야 한다. (1개인 경우는 그릴 수 있나...?)

 

 그래서 입력받은 그래프를 DFS를 통하여 하나의 그래프인지 확인했다.

function DFS(start) {
  let v = new Array(V + 1).fill(false);

  let s = [];
  s.push(start);

  while (s.length) {
    let cur = s.pop();

    if (!v[cur]) {
      v[cur] = true;
      for (let next = 0; next < g[cur].length; next++) {
        s.push(g[cur][next]);
      }
    }
  }

  for (let i = 1; i < v.length; i++) {
    if (!v[i]) return false;
  }
  return true;
}

 

하나의 그래프임이 확인되었다면 모든 정점을 확인해서 각 정점의 차수가 홀수인지 짝수인지 확인 후 결과를 도출한다.

function sol() {
  if (V === 1)  // 지점이 1개 일때.
    return console.log('YES');

  let start;
  for (let i = 1; i <= E; i++) {
    let [a, b] = input[i].trim().split(' ').map(Number)
    g[a].push(b);
    g[b].push(a);
    start = a;
  }

  if (!DFS(start))  // 연결 그래프가 아닌경우.
    return console.log("NO")

  let cnt = 0;
  for (let i = 1; i < g.length; i++) {
    if (g[i].length % 2 !== 0 && g[i].length !== 0) { // 차수가 홀수.
      cnt++;
    }
  }
  if (cnt <= 2)
    return console.log('YES');
  else
    return console.log('NO');
}

 

정점이 1개인 경우는 입력이 어떻게 들어오는지 몰라서 예외로 'YES'로 따로 처리해 주었다.

 

전체코드

/**
 * 그래프 탐색.
 * 오일러 경로. 
 * 연결 그래프에서 차수가 홀수인 정점이 두 개,0개 있다면 그 두 정점을 시작점과 끝점으로 하는 오일러 경로가 존재한다.
 */
const input = require('fs').readFileSync('input.txt').toString().trim().split('\n');
const [V, E] = input[0].split(' ').map(Number);
let g = new Array(3001).fill(null).map(_ => []);

function DFS(start) {
  let v = new Array(V + 1).fill(false);

  let s = [];
  s.push(start);

  while (s.length) {
    let cur = s.pop();

    if (!v[cur]) {
      v[cur] = true;
      for (let next = 0; next < g[cur].length; next++) {
        s.push(g[cur][next]);
      }
    }
  }

  for (let i = 1; i < v.length; i++) {
    if (!v[i]) return false;
  }
  return true;
}
function sol() {
  if (V === 1)  // 지점이 1개 일때.
    return console.log('YES');

  let start;
  for (let i = 1; i <= E; i++) {
    let [a, b] = input[i].trim().split(' ').map(Number)
    g[a].push(b);
    g[b].push(a);
    start = a;
  }

  if (!DFS(start))  // 연결 그래프가 아닌경우.
    return console.log("NO")

  let cnt = 0;
  for (let i = 1; i < g.length; i++) {
    if (g[i].length % 2 !== 0 && g[i].length !== 0) { // 차수가 홀수.
      cnt++;
    }
  }
  if (cnt <= 2)
    return console.log('YES');
  else
    return console.log('NO');
}
sol();

특이사항

 오일러 경로는 '연결 그래프'에 대하여 확인할 수 있다. 이점을 미리 확인해주자.