[BOJ - JAVA] 1707 - 이분 그래프 (BFS)

# 주소

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

1707번: 이분 그래프

# 문제

# 문제 해설 및 코드 리뷰

import java.util.*;
public class Main {
    static int testcase,node,v;
    static int arr[];
    static List<Integer> list[];
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        testcase = scan.nextInt();
        while(testcase-- > 0){
            node = scan.nextInt();
            v = scan.nextInt();
            list = new ArrayList[node+1];
            for(int i = 1; i < node+1; i++){
                list[i] = new ArrayList<>();
            }
            for(int i = 0; i < v; i++) {
                int a = scan.nextInt();
                int b = scan.nextInt();
                list[a].add(b);
                list[b].add(a);
            }
            arr = new int[node+1];
            dfs(1);
        }
    }
    public static void bfs(int x){
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 1; i < node+1; i++){
            if(arr[i] == 0){
                arr[i] = 1;
                queue.offer(i);
            }
            while(!queue.isEmpty()){
                int now = queue.poll();
                for(int j : list[now]){
                    if(arr[j] == arr[now]) {
                        System.out.println("NO");
                        return;
                    }
                    if(arr[j] == 0){
                        queue.offer(j);
                        if(arr[now] == 1){
                            arr[j] = 2;
                        }else
                            arr[j] = 1;
                    }
                }
            }
        }
        System.out.println("YES");
    }
}

이분그래프라는 개념에 대해 먼저 알 필요가 있습니다.

https://terms.naver.com/entry.naver?docId=3405266&cid=47324&categoryId=47324 

이분그래프

지식백과에서 한 번 읽어보시길 바랍니다.

만약 이 포스팅을 보러 오셨다면 이분 그래프에 대해 어느정도 개념은 알지만 코딩 내용에 대해 궁금하신 분들이 많을테니 저도 이분 그래프에 대해 먼저 쓰면서 다시 제대로 개념을 읽히고 말씀드리겠습니다.

이분 그래프는 정점을 기준으로 인접한 다른 점에 연결할 때 완전히 다른 점에 인접해야 합니다.

그러므로 같은 색상의 점끼리는 연결이 될 수 없으며, 같은 색이 나오면 그 BFS함수는 종료하고 NO를 출력합니다.

당연히 같은 색과 인접해 있다는 것은 Cycle이란 뜻으로도 해석이 가능합니다.

코딩 내용을 한 번 살펴보겠습니다.

testcase를 while문으로 하나씩 소거하면서 그 내부에서 본격적으로 문제를 풀어나가겠습니다.

따라서 node를 점의 개수, v를 간선의 수라고 선언했습니다.

list를 new ArrayList<>타입으로 static으로 받아온 것을 이제 선언합니다. (node + 1크기로)

그리고 list[i]를 각각 제각기 선언합니다.

list와 list[i]는 이렇게 생각하시면 좋겠습니다.

list는 ArrayList지만 크기가 node+1로 정해진 배열의 특성을 가진 list라고 생각하시고 

list[i]는 그냥 우리가 알고 있는 일반적인 ArrayList<>라고 생각합니다.(ArrayList는 들어오는 데이터에 따라 크기가 가변적)

이후 for문에서 1 3이 입력된다면 list[1]에는 3을 추가하고 list[3]에는 1을 추가하는 방식으로 

list[a].add(b);
list[b].add(a);

라고 입력합니다.

따라서 최종적으로 1 3, 2 3이 입력된다면 arr[1]에는 3, arr[2]에는 3, arr[3]에는 1, 2가 입력될 것입니다.

이후 우리가 활용할 arr를 node+1크기로 선언하고 bfs에 1을 넣으며 bfs 문을 짜보겠습니다.

 

bfs문은 Queue를 사용하므로 Queue를 일단 선언합니다.

그리고 차례대로 for문에서 i에 대해 arr[i]를 1로 바꾸고 queue에 넣어야 합니다.

그러나 연결되어있는 i에 대해선 밑에서 arr[i]를 다른 값으로 변경할 것이기 때문에 모든 i가 아닌, arr[i] == 0인 값에 한정해서 arr[i]를 0으로 바꾸고 queue에 넣겠습니다.

자 그렇게 queue에 i가 들어갔고 (제일 처음은 1이겠죠?) while문으로 구문을 만듭니다.

int now = queue.poll(); 이 말은 queue에서 제일 먼저 들어간 값을 빼낸 값입니다.

따라서 now는 현재 1입니다.

이때 for문을 통해 No를 출력합니다.

만약, arr[now]가 1이 arr[j]랑 같으면 NO를 출력할 것인데, 제일 처음 now는 1이었으므로 list[1]에 들어간 값을 int j가 조회합니다.

이 j가 될 수 있는 값은 우리가 arr[1]이 3인 것을 위의 예제에서 확인했으므로 j는 3입니다.

따라서 arr[j] == arr[now] 이 말은, arr[3] == arr[1]이랑 같냐 하고 묻는 것과 같습니다.

arr[3]은 아직 0인데, arr[1] == 1이지요? 그럼 return되지 않고 계속 다음으로 넘어가봅시다.

아래의 if문에서 if(arr[j] == 0) -> arr[3] == 0이므로 queue에 3을 넣고, arr[now] == 1이었으므로 arr[3] = 2로 바꿉니다.

자 그럼 queue에는 지금 3이 들어가있고, arr[1] = 1, arr[3] = 2인 상태입니다. 즉,

지금 현재 이런 상태입니다. 계속 살펴봅시다.

제일 위의 while문에서( while문이 아직 종료가 안되었으므로) now = 3이 됩니다.

그리고 list[3]에 해당하는 j는 1이 될 테고 arr[1] == arr[3]인가요? 아니지요? 다른 색이니까요.

그래서 밑의 if문으로 내려가게 되고 arr[j] == 0이 아니므로 while문은 종료됩니다.

다시 제일 위의 for문으로 갑시다.

i = 2가 될테고 arr[2] == 0이므로 arr[2] = 1로 바꾸고 queue에는 2를 삽입합니다.

while문으로 들어가서, now = 2이고 list[2]를 조회합니다.

list[2]에는 들어갈 수 있는 수가... 3이 있네요 (2 3이 Input)

따라서 arr[3] == arr[2]인지도 확인할 것인데, arr[2] = 1이고 arr[3] = 2이므로 return되지 않고 내려갑니다.

아래의 if문에서 arr[3] == 0인가요?? 아니지요? 그럼 while문은 종료가 됩니다. 

마지막으로 제일 위의 for문에서 i = 3일때를 살펴봅시다.

arr[3] == 0이 아니므로 if문이 실행되지 않고 그대로 함수가 종료되어 제일 아래의 YES를 출력합니다.

최종적으로 그림으로 살펴보자면 arr[1] = 1, arr[2] = 1, arr[3] = 2였습니다.

이런 형태가 되겠네요.

어때요? 이분그래프지요?

1과 2는 3과 연결되어있으면서, 1 2는 서로 연결되어 있지 않은 이런 상태를 이분 그래프라고 한답니다.

감사합니다.