[백준] 1707번 - 이분 그래프 (Java)

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

1707번: 이분 그래프

 

<문제 분석>

1. 먼저 이분그래프에 대해 알아보자.

2. 인접한 정점은 다른 색상으로 저장하자. (1 or 2)

3. 방문하려는데 동일한 색상이 이미 칠해져 있으면 이분그래프가 아니다.

4. DFS(정점번호, 색상)을 넘겨주자.

 

<코드 구현 - 인접행렬&DFS>

import java.util.*;

/*
[백준] 1707번 - 이분 그래프 (Java)
*/

public class Main {
    static int K, V, E;
    static int map[][];
    static int visited[];

    static boolean DFS(int node, int color) {
        visited[node] = color;

        // 루프가 있으면 이분그래프가 아니다.
        if (map[node][node] == 1) return false;

        for (int i=1; i<=V; i++) {
            // 인접 노드인데 색상이 같으면 이분 그래프가 아니다.
            if (map[node][i] == 1 && visited[node] == visited[i])
                return false;

            // 인접 노드인데 방문 안했으면 탐색 계속
            if (map[node][i] == 1 && visited[i] == 0) {
                if (color == 1)// 현재와 다른 색상으로 칠함.
                    return DFS(i, 2);
                else
                    return DFS(i, 1);
            }
        }
        return true;
    }

    void Solve() {
    }

	public static void main(String[] args) {
        Main m = new Main();
        //m.InputData();
        Scanner in = new Scanner(System.in);
        K = in.nextInt();
        for (int i=0; i<K; i++) {
            V = in.nextInt();
            E = in.nextInt();
            map = new int[V+1][V+1];
            visited = new int[V+1];
            for (int j=1; j<=E; j++) {
                int x = in.nextInt();
                int y = in.nextInt();
                map[x][y] = 1;
                map[y][x] = 1;
            }
            boolean ans = DFS(1, 1);
            // for (int x : visited)
                // System.out.print(x+" ");
            if (ans)
                System.out.println("YES");
            else
                System.out.println("NO");
            
        }

	}

    // // DEBUG
    // static void PrintMap() {
    //     for (int i=0; i<M; i++) {
    //         for (int j=0; j<M; j++) {
    //             System.out.print(map[i][j]+" ");
    //         }
    //         System.out.println();
    //     }
    // }
    
}

 

<제출 결과 -메모리 초과>

 

<원인 분석>

1. 재귀호출을 할 때, return DFS()로 했더니 중간에 stack에서 나가버렸다.

  그래서, dfs 결과값을 전역변수(result)에 중간중간 저장하는 방식으로 변경했다.

2. TC가 여러개일 때 result를 초기화 해주기 않아서 이전 값이 출력되었다.

 

<코드 구현 - 인접리스트>

import java.util.*;

/*
[백준] 1707번 - 이분 그래프 (Java)
*/

public class Main {
    static int K, V, E;
    static ArrayList<Integer> list[];
    static int visited[];
    static String result = "";

    static boolean DFS(int node, int color) {
        visited[node] = color;

        for (int v : list[node]) {
            //System.out.println("list["+node+"] -> "+v+", color= "+color);
            if (visited[v] == 0) {
                DFS(v, color*-1);
            } else if (visited[v] == visited[node]) {
                result = "NO";
                return false;
            }
            if (result.equals("NO")) {
                return false;
            }
        }
        result = "YES";
        return true;
    }

	public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        K = in.nextInt();
        for (int i=0; i<K; i++) {
            result = "";// 결과값 초기화
            V = in.nextInt();
            E = in.nextInt();
            list = new ArrayList[V+1];
            for (int j=1; j<=V; j++) {
                list[j] = new ArrayList<>();
            }
            visited = new int[V+1];
            for (int k=1; k<=E; k++) {
                int s = in.nextInt();
                int e = in.nextInt();
                list[s].add(e);
                list[e].add(s);
            }
            boolean ans = true;
            for (int t=1; t<=V; t++) {
                if (visited[t] == 0) {
                    ans = DFS(t, 1);
                }
                if (ans == false) break;//그래프가 여러개일 때 하나라도 이분그래프가 아니면 중지
            }
            System.out.println(result);
        }
	}
}

<제출 결과>