[do it 알고리즘] 백준1707 (그래프의 표현)

그래프란?

• 객체 사이의 연결 관계를 표현할 수 있는 자료구조
• 정점(vertex)과 간선(edge)들의 집합
• 종류는 무방향 그래프, 방향 그래프

문제 설명

 

강의 코드

import java.io.BufferedReader;
import java.util.ArrayList;
import java.io.InputStreamReader;
public class Baek1707 {
    static ArrayList<Integer>[] A;
    static int[] check; // 같은 집합인지 다른집합인지 구분
    static boolean[] visited; // 방문 여부
    static boolean IsEven; // 이분 그래프 인지 아닌지 T / F

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCase = Integer.parseInt(br.readLine());
        for(int k = 0; k < testCase; k++) { // 주어진 테스트 케이스 만큼
            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); // 방향 X
                A[end].add(start);
            }
            // 모든 노드에서 dfs 실행
            for (int i = 1; i <= V; i++){
                if(IsEven){
                    DFS(i);
                }else{
                    break;
                }
            }
            if(IsEven){
                System.out.println("YES");
            }else{
                System.out.println("NO");
            }
        }
    }
    public static void DFS(int start){
        visited[start] = true;
        for(int i : A[start]){ //start에서 연결된 모든 노드 탐색
            if(!visited[i]) {
                // 그 전에 있는 노드와 다른 집합으로 분류
                check[i] = (check[start] + 1) % 2; // 토글 방식으로 0 / 1로 분류 구분
                DFS(i);
            }else if(check[start]==check[i]){
                    IsEven = false;
            }
        }
    }
}

이분 그래프란?

• 집합을 둘로 나눠 같은 집합끼리는 인접하지 않는 그래프

강의 코드 설명 및 해석

• 입력된 그래프 데이터는 가중치가 없으므로 인접 리스트로 구현
• 그래프를 따라 이어나가므로 DFS를 실행
• DFS는 모든 노드에서 각각 실행, 그 이유는 그래프가 다 이어져있다는 보장이 없기 때문
• 무방향 그래프이므로 start와 end 교차로 추가
• check배열을 0과 1로 그룹을 나누고, 바로 직전 방문 그룹과 현재 그룹이 같으면 이분 그래프 X

골4는 아직 너무 어렵..