백준 - 1707 이분 그래프

Park Inhye·2024년 3월 22일

코테 연습

목록 보기

25/37

문제

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.

입력

첫째 줄
- 테스트케이스 개수 K
M개의 줄
- 정점의 개수 N
- 간선의 개수 E
- 간선이 연결하는 두 정점의 번호 (u와 v)

제한 조건

2 ≤ K ≤ 5
1 ≤ V ≤ 20,000
1 ≤ E ≤ 200,000

예시

// NOTE: 입력
2
3 2
1 3
2 3
4 4
1 2
2 3
3 4
4 2

// NOTE: 출력
YES
NO

해결

헤맨 부분

테스트 케이스 구분
- V와 E 다음 줄 ~ 간선 갯수

```
// NOTE: 입력

2 ---------------- K(테스트 케이스 갯수)
3 2 -------------- 🔥 Case1의 V(정점 3개)와 E(간선 2개)
1 3
2 3
4 4 -------------- 🔥 Case2의 V(정점 4개)와 E(간선 4개)
1 2
2 3
3 4
4 2
```

색상 상수 처리

색상은 절대 변하면 안되니까 COLOR라는 객체를 만들고 Freeze 처리했다.
```
const COLOR = Object.freeze({
    a: 1,
    b: 2,
});
```

makeGraphMap

그래프 생성하는 코드블록

Map으로 그래프를 만들었다.
- 값의 여부 확인이 쉽고 속도가 빠르기 때문이다.

const makeGraphMap = (inputData) => {
    const _map = new Map();

    for (let input of inputData) {
        const [_from, _to] = input.split(' ').map(Number);

        if (!_map.has(_from)) _map.set(_from, []);
        if (!_map.has(_to)) _map.set(_to, []);

        _map.get(_from).push(_to);
        _map.get(_to).push(_from);
    }

    return _map; 
};

bfs

bfs 탐색하며, true 아니면 false 출력
방문 여부 확인하는 배열
- value: COLOR 값으로 변경
- color[node] == null
  - 방문하지 않은 정점
  - value 지정 후 queue에 정점 push
- color[node] != _nextColor
  - 이미 색상이 지정되어 있고 다음 색상과 다른 경우
  - 이분 그래프가 아니므로 return false

모든 탐색이 잘 끝나면 return true

const bfs = (graph, startNode, colorArr) => {
    const _queue = [startNode];

    while (_queue.length) {
        const _cur = _queue.shift();
        const _nextColor = colorArr[_cur] == COLOR.a ? COLOR.b : COLOR.a;

        if (!graph.has(_cur)) break;

        for (let node of [...graph.get(_cur)]) {
            if (!colorArr[node]) {
                colorArr[node] = _nextColor;
                _queue.push(node);
                continue;
            }

            if (colorArr[node] != _nextColor) {
                return false;
            }
        }
    }

    return true;
};

checkBipartiteGraph

입력 데이터 변수에 저장

테스트 케이스를 잘라냄

첫 줄을 shift
- N(정점 갯수), V(간선 갯수)
0 ~ 간선 갯수까지 splice
colorArray 생성 (bfs에서 방문여부 + nextColor 비교)
반복문
- 이미 방문했던 정점이면 지나가기
- 첫 정점의 색상 지정
- bfs 탐색하며 return false인 경우, 플래그 false로 바꾸고 반복 종료
flag 값에 따라 YES / NO 출력

function checkBipartiteGraph() {
    let [K,..._inputs] = require('fs')
        .readFileSync('dev/stdin')
        .toString()
        .trim()
        .split(/\n/);
    K = +K;

    while(K--) {
        const [N, V] = _inputs.shift().split(' ').map(v => +v);
        const _graph = makeGraphMap(_inputs.splice(0,V));
        const _colorArr = new Array(N + 1).fill(null);
        let _flag = true;

        for (let i = 1; i <= N + 1; i++) {
            if (_colorArr[i]) continue;

            _colorArr[i] = COLOR.a;

            if (!bfs(_graph, i, _colorArr)){
                _flag = false;
                break;
            }
        }

        _flag ? console.log('YES') : console.log('NO');
    }
}

전체 코드

// NOTE: 상수
const COLOR = Object.freeze({
    a: 1,
    b: 2,
});

// NOTE: solution
const makeGraphMap = (inputData) => {
    const _map = new Map();
    
    for (let input of inputData) {
        const [_from, _to] = input.split(' ').map(Number);
    
        if (!_map.has(_from)) _map.set(_from, []);
        if (!_map.has(_to)) _map.set(_to, []);
        
        _map.get(_from).push(_to);
        _map.get(_to).push(_from);
    }
    
    return _map; 
};

const bfs = (graph, startNode, colorArr) => {
    const _queue = [startNode];

    while (_queue.length) {
        const _cur = _queue.shift();
        const _nextColor = colorArr[_cur] == COLOR.a ? COLOR.b : COLOR.a;
        
        if (!graph.has(_cur)) break;
        
        for (let node of [...graph.get(_cur)]) {
            if (!colorArr[node]) {
                colorArr[node] = _nextColor;
                _queue.push(node);
                continue;
            }
            
            if (colorArr[node] != _nextColor) {
                return false;
            }
        }
    }

    return true;
};

function checkBipartiteGraph() {
    let [K,..._inputs] = require('fs')
        .readFileSync('dev/stdin')
        .toString()
        .trim()
        .split(/\n/);
    K = +K;
    
    while(K--) {
        const [N, V] = _inputs.shift().split(' ').map(v => +v);
        const _graph = makeGraphMap(_inputs.splice(0,V));
        const _colorArr = new Array(N + 1).fill(null);
        let _flag = true;
        
        for (let i = 1; i <= N + 1; i++) {
            if (_colorArr[i]) continue;
        
            _colorArr[i] = COLOR.a;
        
            if (!bfs(_graph, i, _colorArr)){
                _flag = false;
                break;
            }
        }
        
        _flag ? console.log('YES') : console.log('NO');
    }
}

checkBipartiteGraph();