[백준] 1707번 : 이분 그래프 - JAVA [자바]

https://www.acmicpc.net/problem/1707

---

먼저 이분 그래프에 대해서 알아야 한다.

이분 그래프란 어떠한 노드에서 인접한 노드를 탐색할 때, 인접한 노드를 현재 노드와 다른 색으로 색칠한다.
모든 노드 탐색하며 노드를 칠하고 난 뒤 사용한 색이 단 두가지 일때 이 그래프는 이분 그래프라고 할 수 있다.

이러한 개념을 가지고 알고리즘을 사용한다면 현재 노드에서 인접한 모든 노드들을 다른 색으로 칠하면서 탐색하다가 인접한 노드가 이미 칠해졌으며 현재 노드와의 색이 같다면 이분 그래프가 아니라는 것을 판단하면 된다.

즉, bfs 알고리즘을 사용하면 된다.

// 레드 : 1, 블루 : -1, 아직 색칠하지 않음 : 0
color = new int[V + 1];            

우선 색을 어떻게 나타낼까 하다가 int[] 배열로 값이 0 이면 아직 칠하지 않은것 1 이면 빨간색 -1 이면 파란색으로 생각하고 풀었다.

private static boolean bfs(int start) {
	Queue<Integer> queue = new LinkedList<>();
    queue.add(start);
    color[start] = 1;

	while (!queue.isEmpty()) {
    	start = queue.poll();
        for (int to : edgeList.get(start)) {
            // 아직 색칠이 되지 않았으면
            if (color[to] == 0) {
            	queue.add(to);
                color[to] = color[start] * -1;
			}
        	// 같은 색으로 칠해져 있으면 이분 그래프가 아니므로 종료
            if (color[to] == color[start]) {
            	return false;
			}
		}
	}
    return true;
}

1. 시작하는 노드를 인자로 받는다.
2. bfs를 위한 queue를 생성한다.
3. 현재 start 를 queue 에 add 한다.
4. start 의 색을 1(빨간색)으로 지정한다.
5. queue 에서 poll 을 한다.
6. 나온 수를 start 에 대입한다.
7. start 와 인접한 노드들을 탐색한다.
8. 아직 칠해지지 않았다면 queue 에 add 하고 color 를 start 의 반대 색(현재색 x -1)을 대입한다.
   8.1 만약 현재 색이 칠해져 있으며 같은 색이라면 이분 그래프가 안되므로 false 를 return 하고 종료한다.
9. 모든 인접한 노드들을 start 색과 다른 색으로 다 칠했으면 queue 에서 새로 poll 한 수(start에서 가장 먼저 탐색한 인접한 노드)를 start 로 대입한다.
10. 7번부터 다시 반복한다.
11. 모든 노드를 탐색하며 인접한 노드가 같은 색인 경우가 없다면 이분 그래프이니 true를 return 한다.

boolean yes = false;
for (int i = 1; i <= V; i++) {
   	if (color[i] == 0) {
    	yes = bfs(i);
	}
	if (!yes) break;
}

시작하는 노드를 1번 부터 V 까지 돌아가며 그래프를 탐색하며 이분 그래프가 아닌 경우를 발견하면 조기 종료한다.

public static ArrayList<ArrayList<Integer>> edgeList;
edgeList = new ArrayList<>();
for (int i = 0; i < V + 1; i++) {
	edgeList.add(new ArrayList<>());
}

간선의 정보를 이차원 리스트에 저장해야 한다.
아니면 시간 초과가 발생한다.

---

public class bj1707 {

    public static int V;
    public static int E;
    public static ArrayList<ArrayList<Integer>> edgeList;
    public static int[] color;

    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int K = Integer.parseInt(br.readLine());
        for (int k = 0; k < K; k++) {

            String line = br.readLine();
            String[] split = line.split(" ");

            V = Integer.parseInt(split[0]);
            E = Integer.parseInt(split[1]);
            // 레드 : 1, 블루 : -1, 아직 색칠하지 않음 : 0
            color = new int[V + 1];

            edgeList = new ArrayList<>();
            for (int i = 0; i < V + 1; i++) {
                edgeList.add(new ArrayList<>());
            }

            for (int i = 0; i < E; i++) {
                String line1 = br.readLine();
                String[] split1 = line1.split(" ");
                int from = Integer.parseInt(split1[0]);
                int to = Integer.parseInt(split1[1]);
                edgeList.get(from).add(to);
                edgeList.get(to).add(from);
            }
            boolean yes = false;
            for (int i = 1; i <= V; i++) {
                if (color[i] == 0) {
                    yes = bfs(i);
                }
                if (!yes) break;
            }

            if (yes) bw.write("YES\n");
            else bw.write("NO\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }

    private static boolean bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        color[start] = 1;

        while (!queue.isEmpty()) {
            start = queue.poll();
            for (int to : edgeList.get(start)) {
                // 같은 색으로 칠해져 있으면 이분 그래프가 아니므로 종료
                if (color[to] == color[start]) {
                    return false;
                }
                // 아직 색칠이 되지 않았으면
                if (color[to] == 0) {
                    queue.add(to);
                    color[to] = color[start] * -1;
                }
            }
        }
        return true;
    }
}