[백준] 12893_적의 적 (Javascript)

문제

BOJ12893_적의 적

코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [N, M] = input[0].split(' ').map(Number);
const arr = input.slice(1).map((e) => e.split(' ').map(Number));
const graph = Array.from({ length: N + 1 }, () => []);
arr.forEach(([a, b]) => {
    graph[a].push(b);
    graph[b].push(a);
});
// 방문하지 않은 노드 = 0, 방문한 노드 = 1, -1
const visited = Array(N + 1).fill(0);

function bfs(cur) {
    // 방문하지 않은 노드라면
    if (visited[cur] === 0) {
        const queue = [cur];
        let front = 0;
        visited[cur] = 1;
        while (queue.length > front) {
            const v = queue[front++];
            for (let next of graph[v]) {
                if (visited[next] === 0) {
                    visited[next] = visited[v] * -1; // 적대 관계인 노드는 반대 부호
                    queue.push(next);
                } else if (visited[next] === visited[v]) return 0;
            }
        }
    }
}

let answer = 1;
for (let i = 1; i <= N; i++) {
    if (bfs(i) === 0) {
        answer = 0;
        break;
    }
}

console.log(answer);

풀이

문제를 그림으로 보면 아래와 같다고 볼 수 있다.

같은 부호를 갖는 노드들 끼리는 우호 관계이고, 부호가 반대라면 적대 관계이다.

입력으로 들어오는 적대관계 정보를 이용해서 그래프를 만들면 그래프의 각 노드는 적대관계인 노드와 인접하게 된다.
그런 다음 모든 노드를 순회하며 인접 노드중 방문하지 않은 노드가 있다면 자신과 다른 부호를 갖도록 만들어준다.
만약 인접한 노드의 부호가 자신과 같다면 '적의 적은 친구 이론'이 성립하지 않는 것이므로 0을 반환하고 반복을 종료한다.

참고

• 문제 풀이
• 문제 풀이