[백준] 16168 퍼레이드 (Javascript)

문제

BOJ16168_퍼레이드

풀이

1. 이미 방문한 간선을 다시 방문하면 안된다.

2. 방문한 노드를 다시 방문하는 것은 상관없다.

3. 즉, 한 붓 긋기가 가능한지 물어보는 문제다.

4. 오일러 알고리즘을 적용해볼 수 있다.

5. 그래프가 하나의 컴포넌트로 이어져있어야 한다.

6. 주어진 그래프는 무방향 그래프이고,

7. 오일러 회로든 오일러 경로든 아무거나 적용해도 상관없다.

8. 오일러 회로가 아닌 오일러 경로는 두 정점의 차수가 홀수이면서, 나머지 정점의 차수는 짝수여야 한다.

9. 오일러 회로는 모든 정점의 차수가 짝수여야 한다.

10. 즉, 모든 정점 중 차수가 홀수인 정점이 2개이거나, 홀수인 정점이 아예 없어야 하고, 하나의 컴포넌트로 연결되어 있으면 정답이고, 아니면 오답이다.

11. 입력으로 들어오는 간선 정보를 토대로 각 정점의 차수를 구한다.

12. 차수가 홀수인 정점의 개수를 카운트한다.

13. 유니온 파인드를 통해 모든 정점이 하나의 컴포넌트로 연결되어 있는지 확인한다.

14. 10번의 조건에 맞으면 YES를, 아니라면 NO를 출력한다.

코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [v, e] = input[0].split(' ').map(Number);
const arr = input.slice(1).map((e) => e.split(' ').map(Number));
const degree = Array(v + 1).fill(0);
const parent = Array.from({ length: v + 1 }, (_, i) => i);
arr.forEach(([s, e]) => {
    union(s, e);
    degree[s]++;
    degree[e]++;
});

// 오일러 회로이거나 오일러 경로인지 판별
// 차수가 홀수인 정점이 2개가 넘으면 오일러 회로, 오일러 경로가 될 수 없음
let odd = 0;
for (let i = 1; i <= v; i++) {
    if (degree[i] % 2 === 1) odd++;
}

let same = find(1);
for (let i = 2; i <= v; i++) {
    // 하나의 컴포넌트로 연결되어있지 않다면
    if (find(i) !== same) {
        console.log('NO');
        process.exit();
    }
}

if (odd === 2 || odd === 0) console.log('YES');
else console.log('NO');

function find(x) {
    if (parent[x] !== x) parent[x] = find(parent[x]);
    return parent[x];
}

function union(a, b) {
    a = find(a);
    b = find(b);
    parent[b] = a;
}