[백준 1707, Java] 이분 그래프

문제

www.acmicpc.net/problem/1707

1707번: 이분 그래프

 

풀이

이분그래프가 뭔지 모르겠어서 위키에 있는 설명 보고 풀었다. 

ko.wikipedia.org/wiki/%EC%9D%B4%EB%B6%84_%EA%B7%B8%EB%9E%98%ED%94%84

이분 그래프 - 위키백과, 우리 모두의 백과사전

 

틀렸던 포인트

1. 메모리 초과

원인

연결관계를 boolean[][], 2차원 배열로 선언했다. 그랬더니 메모리초과가 났다. 

boolean 은 1바이트, 배열의 최대 크기는 20,000 * 20,000 = 400,000,000 바이트 = 400,000KB = 400 MB 이므로 문제의 메모리 제한에 어긋난다

 

해결

ArrayList[] 로, 연결 요소만 저장했다.

 

틀린코드

link = new boolean[V+1][V+1];
colors = new int[V+1];

for(int e = 0; e<E; e++){
	st = new StringTokenizer(br.readLine()," ");
	int node1 = Integer.parseInt(st.nextToken());
	int node2 = Integer.parseInt(st.nextToken());
	link[node1][node2] =true;
	link[node2][node1] =true;
}

 

해결 코드

links = new ArrayList[V+1];
colors = new int[V+1];
for(int e = 0; e<E; e++){
	st = new StringTokenizer(br.readLine()," ");
	int node1 = Integer.parseInt(st.nextToken());
	int node2 = Integer.parseInt(st.nextToken());


	if(links[node1] == null){
		links[node1] = new ArrayList<>();
	}
	links[node1].add(node2);

	if(links[node2] == null){
		links[node2] = new ArrayList<>();
	}
	links[node2].add(node1);
}

 

2. 모든 정점이 연결그래프 라고 생각

 

반례

1

100 3

1 2

3 4

5 6

 

"YES"

 

해결

처음 한 정점에서만 dfs 시작 -> 방문 하지 않은 모든 정점에 대해서 dfs 

 

틀린코드

colors[startNode] = RED;
painting(startNode, 1);

 

해결코드

 //노드 색칠하기
for(int v = 1; v<=V; v++){
    if(links[v]!=null && colors[v]==EMPTY){
        colors[v] = RED;
        painting(v, 1);
    }
 }

 

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int K;
    static int V;
    static int E;
    static ArrayList<Integer>[] links;
    static int[] colors;
    static final int EMPTY = 0;
    static final int RED = 1;
    static final int BLUE = 2;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        K = Integer.parseInt(br.readLine());
        for(int k = 0; k<K;k++){
            st = new StringTokenizer(br.readLine()," ");
            V = Integer.parseInt(st.nextToken());
            E = Integer.parseInt(st.nextToken());

            links = new ArrayList[V+1];
            colors = new int[V+1];
            for(int e = 0; e<E; e++){
                st = new StringTokenizer(br.readLine()," ");
                int node1 = Integer.parseInt(st.nextToken());
                int node2 = Integer.parseInt(st.nextToken());


                if(links[node1] == null){
                    links[node1] = new ArrayList<>();
                }
                links[node1].add(node2);

                if(links[node2] == null){
                    links[node2] = new ArrayList<>();
                }
                links[node2].add(node1);
            }

            //노드 색칠하기
            for(int v = 1; v<=V; v++){
                if(links[v]!=null && colors[v]==EMPTY){
                    colors[v] = RED;
                    painting(v, 1);
                }
            }

            //같은 색깔끼리 연결확인
            String result = check();
            bw.write(result);
        }
        bw.flush();
    }
    public static void painting(int node, int count){
                for(int i = 0; i<links[node].size(); i++){
                    int linkNode = links[node].get(i);
                    if(colors[linkNode]==EMPTY){
                        colors[linkNode] = colors[node]==RED? BLUE : RED;
                        painting(linkNode,count+1);
                    }
                }


    }

    public static String check(){
        for(int v =1; v<=V; v++){
            if(links[v] !=null){
                for(int i = 0; i<links[v].size(); i++){
                    if(colors[v] == colors[links[v].get(i)]){
                        return "NO\n";
                    }
                }
            }
        }
        return "YES\n";
    }
}