백준 1707 이분그래프 JAVA

그래프 이론에서 이분 그래프(二分graph, 영어: bipartite graph)란 모든 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 그래프이다.

이문제는 DFS, BFS 둘다 풀 수 있다. 어짜피 모든 꼭지점을 다 돌아야해서 그런 것 같다.

1. DFS

	private static void dfs(int index, int c) {
        if (color[index] != 0) {
            return;
        }
        color[index] = c;
        for (int x : list[index]) {
            dfs(x, 3 - c);
        }
    }

color 는 사용자 방문 전 색상이 선택되기 전이다. 처음엔 모두 0이 될 거기 때문에 0이 아니게 될때까지 반복하는 것이다. 그 다음 색상을 인덱스마다 지정하고 3-c는 0이 아닌 두가지 꼭지점 밖에 존재하지 않기 때문에 설정되며 0 이 아닌 숫자가 반복될때까지 반복 될 것이다.

2. BFS

	private static void bfs(int index, int c) {
        Queue<Integer> q = new LinkedList<>();
        q.add(index);
        color[index] = c;
        while (!q.isEmpty()) {
            int x = q.remove();
            for (int e : list[x]) {
                if (color[e] == 0) {
                    color[e] = 3 - color[x];
                    q.add(e);
                }
            }
        }
    }

전체 풀이

Reference

• 위키피디아