[Do It! 코딩테스트 자바편(김종관)] 문제 048(백준 1707번)

난이도

교재에서 1~2단계 설명을 보고 이를 바탕으로 코드를 짰다. 하지만 시간 초과가 뜨고, 수정하니 틀렸다고 해서 교재 코드까지 다 본 후, 다시 내 코드를 수정해서 간신히 성공했다.

문제

이분 그래프 (백준: 1707번)

교재 풀이(DFS)

• 교재 풀이는 DFS를 가지고 풀었다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
public class P1707_이분그래프 {
  static ArrayList<Integer>[] A;
  static int[] check;
  static boolean visited[];
  static boolean IsEven;
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());
    for (int t = 0; t < N; t++) {
      String[] s = br.readLine().split(" ");
      int V = Integer.parseInt(s[0]);
      int E = Integer.parseInt(s[1]);
      A = new ArrayList[V + 1];
      visited = new boolean[V + 1];
      check = new int[V + 1];
      IsEven = true;
      for (int i = 1; i <= V; i++) {
        A[i] = new ArrayList<Integer>();
      }
      for (int i = 0; i < E; i++) { // 인접 리스트로 그래프 저장
        s = br.readLine().split(" ");
        int Start = Integer.parseInt(s[0]);
        int End = Integer.parseInt(s[1]);
        A[Start].add(End);
        A[End].add(Start);
      }
      for (int i = 1; i <= V; i++) { // 주어진 그래프가 하나로 연결되어 있다는 보장이 없으므로 모든 정점에서 수행
        if (IsEven)
          DFS(i);
        else
          break;
      }
      check[1] = 0;
      if (IsEven)
        System.out.println("YES");
      else
        System.out.println("NO");
    }
  }
  public static void DFS(int node) { // DFS구현
    visited[node] = true;
    for (int i : A[node]){
      if (!visited[i]) {
        check[i] = (check[node] + 1) % 2; // 인접한 정점은 같은 집합이 아니므로 이전 정점과 다른 집합으로 처리
        DFS(i);
      }
      else if (check[node] == check[i]){ // 이미 방문한 정점이 현재 내 정점과 같은 집합이면 이분 그래프가 아님
        IsEven = false;
      }
    }
  }
}

내 풀이(BFS)

• 내 풀이는 BFS를 가지고 풀었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int testCnt;
    static int nodeCnt, edgeCnt;
    static ArrayList<Integer>[] list;
    static boolean[] visited;
    static int[] check;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        testCnt = Integer.parseInt(st.nextToken());
        for (int i = 0; i < testCnt; i++) {
            st = new StringTokenizer(br.readLine());
            nodeCnt = Integer.parseInt(st.nextToken());
            edgeCnt = Integer.parseInt(st.nextToken());

            // list 초기화
            list = new ArrayList[nodeCnt + 1];
            for (int j = 1; j <= nodeCnt; j++) {
                list[j] = new ArrayList<Integer>();
            }
            for (int j = 0; j < edgeCnt; j++) {
                st = new StringTokenizer(br.readLine());
                int s = Integer.parseInt(st.nextToken());
                int e = Integer.parseInt(st.nextToken());
                list[s].add(e);
                list[e].add(s);
            }

            // isBipartite 수행
            boolean res = true;
            visited = new boolean[nodeCnt + 1];
            check = new int[nodeCnt + 1];
            for (int j = 1; j <= nodeCnt; j++) {
                res = isBipartite(j);
                if (res == false)
                    break;
            }

            // 판별 결과 출력
            if (res == false) {
                System.out.println("NO");
            } else {
                System.out.println("YES");
            }
        }
    }

    private static boolean isBipartite(int start) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visited[start] = true;

        boolean res = true;// true라 가정
        while (!queue.isEmpty()) {
            int now = queue.poll();
            for (int tmp : list[now]) {
                if (!visited[tmp]) {
                    queue.add(tmp);
                    visited[tmp] = true;
                    check[tmp] = (check[now] + 1) % 2;
                }

                if (check[tmp] == check[now]) {
                    res = false;
                    return res;
                }
            }
        }

        return res;
    }
}