[java 백준] 골드 4/ 1707번 이분 그래프

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

1707번: 이분 그래프

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class Main {
    static ArrayList<ArrayList<Integer>> arr;
    static int[] result;
    static int[] visit;
    static Scanner sc = new Scanner(System.in);
 
    static final int RED = 1;
    static final int BLUE = -1;
    static boolean graph = true;
 
    public static void bfs(int x, int color) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(x);
        visit[x] = color;
 
        while (!queue.isEmpty() && graph) {
            int v = queue.poll();
 
            for (int i : arr.get(v)) {
                if (visit[i] == 0) {
                    queue.offer(i);
                    visit[i] = visit[v] * -1;
                } else if (visit[v] + visit[i] != 0) {
                    graph = false;
                    return;
                }
            }
        }
 
    }
 
    public static void main(String[] args) {
 
        int k = sc.nextInt();
        for (int i = 0; i < k; i++) {
            int v = sc.nextInt();
            int e = sc.nextInt();
            graph = true;
            visit = new int[v + 1];
            arr = new ArrayList<>();
            for (int i1 = 0; i1 < v + 1; i1++) {
                arr.add(new ArrayList<Integer>());
                visit[i1] = 0;
 
            }
            for (int j = 0; j < e; j++) {
                int a = sc.nextInt();
                int b = sc.nextInt();
 
                arr.get(a).add(b);
                arr.get(b).add(a);
            }
 
            for (int i1 = 1; i1 <= v; i1++) {
                if (!graph) {
                    break;
                }
                if (visit[i1] == 0) {
                    bfs(i1, RED);
                }
            }
            System.out.println(graph ? "YES" : "NO");
 
        }
 
    }
 
}
 

 

코드 설명

---

 

이 문제는 ArrayList를 사용하는 것이 매우 중요하다. 원래는 지조있게 배열로 풀려고 했으나 시간초과가 나와서 결국 ArrayList를 사용했다. ArrayList를 사용하는데 있어서 2가지 중요한 사항이 있는데 이것을 아래에서 설명하겠다.

 

1) 2차원 ArrayList 사용

 

2차원 ArrayList를 사용해본적이 없어서 처음에 굉장히 헤맸다.

static ArrayList<ArrayList<Integer>> arr;

--> <T>안에 ArrayList<Integer>를 한번 더 써준다.

 

 

for (int i1 = 0; i1 < v + 1; i1++) {

                arr.add(new ArrayList<Integer>());

                visit[i1] = 0;

 

            }

 

-->2차원 리스트를 만들어 주기 위해 안에 다시 ArrayList를 넣어준다. 이게 지금 보면 잘 안와닿는데 예를 들어 설명해보자면 

 

정점 1이 정점 2,3과 각각 연결되어있다고 가정해보자.

그러면 정점 1이 기준이기에 1이 행이 된다.

즉 arr.get(1)을 하면 행인 1과 인접한 열, 즉 정점 1과 인접한 2,3이 arr[1]인 리스트 안에 들어가게 된다.  

 print(arr.get(1)) 을 하면 [2,3]으로 출력된다.

 

2) for(int i:arr) 형태를 변형하여 인접한 정점들 순회 

 

for(int i:arr) 을 하면 arr배열의 처음부터 끝까지 순회를 한다. 

아까 말했던 인접한 정점을 리스트에 넣어줬으니 얘네를 순회하면서 같은 색깔이면 false, 다른 색깔이면 true를 유지해준다. 

 

예를 들어 정점이 3개 있고, 간선이 2개가 있다.

 

정점은 1부터 3까지 간선은 (1,3) (2,3) 사이에 있다.

 

이걸 bfs로 풀면

 

1->3->2 순으로 움직인다. 

 

[3]은 1이 3과  인접해있다는 것이고,

[1,2]는 3이 1과 2랑 인접해 있다는 것이고,

[3]은 2가 3이랑 인접해 있다는 것이다. 

 

(1->3->2 의 순서를 따른다. )

 

이분 그래프란 무엇일까?!

---

 

그럼 이분 그래프란 무엇일지 궁금해진다. 사실 이걸 먼저 설명했어야 하는데 ㅋㅋㅋ

 

이분그래프의 정확한 정의는 아래 첨부해둔 사이트 또는 구글링으로 더 자세히 살펴보고, 이 문제를 풀기위한 이분그래프의 개념에 대해서 내가 이해한만큼 간단히 설명해보겠다. 

 

예를 들어 정점 1,2,3,4 가 있고

(1,2) ->(2,3) ->(3,4) ->(4,2) 순으로 움직인다. 움직인다는 것은 간선이 있다는 것을 의미한다.

 

1이 파란색을 칠하면 그 다음 목적지인 2에는 빨간색이 칠해진다. (파->빨)

2에서 다음 목적지인 3에 가면서 3에는 파란색이 칠해진다. (빨->파)

3에서 다음 목적지인 4에 가면서 4에는 빨간색이 칠해진다. (파->빨)

4에서 다음 목적지인 2에 가는데 빨강에서 빨강으로 간다. 즉 같은 색깔로 움직이게 되면 이것은 이분그래프가 아니다. 

 

처음 썼던 코드 + 틀린 이유 정리 

---

import java.io.IOException;
import java.util.Scanner;
 
public class Main {
    static int[][] arr;
    static int[] visit;
 
    final static int RED = 1;
    final static int BLUE = -1;
    static boolean graph = true;
 
    public static void dfs(int x, int color, int len) {
        if (x <= len) {
            visit[x] = color;
 
            for (int i : arr[x]) {
 
                if (visit[i + 1] == color && arr[x - 1][i] == 1) {
                    graph = false;
                    break;
                } else if (visit[i] == 0 && i < len) {
                    dfs(i, -color, len);
                }
            }
        }
 
    }
 
    public static void main(String[] args) throws IOException {
 
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        for (int i = 0; i < k; i++) {
            int v = sc.nextInt();
            int e = sc.nextInt();
            final int LEN = v;
            arr = new int[v][v];
            visit = new int[v + 1];
 
            for (int j = 1; j <= e; j++) {
                int a = sc.nextInt();
                int b = sc.nextInt();
 
                arr[a - 1][b - 1] = 1;
                arr[b - 1][a - 1] = 1;
            }
 
            for (int i1 = 0; i1 < v; i1++) {
                if (!graph) {
                    break;
                }
                if (visit[i1] == 0) {
                    dfs(i1, RED, LEN);
                }
            }
            System.out.println(graph ? "YES" : "NO");
 
        }
 
    }
 
}

 

dfs+ 배열 조합으로 풀었는데 메모리 초과가 떴다.

 

인접한 정점만 모아놓은 배열만 순회하는게 아니라 처음부터 끝까지 순회하니 틀릴 수 밖에 없었다...

참고사이트

---

https://jellyinghead.tistory.com/14

[백준 1707] 이분 그래프 (자바)

https://gmlwjd9405.github.io/2018/08/23/algorithm-bipartite-graph.html

[알고리즘] 이분 그래프(Bipartite Graph)란 - Heee's Development Blog