[ 그래프 ] 그래프(백준 1707)

 그래프

그래프는 노드와 에지로 구성된 집합이다.

노드는 데이터를 표현하는 단위, 에지는 노드를 연결하는 선

• 유니온 파인드 : 그래프의 사이클이 생성되는지 판별하는 알고리즘
• 위상정렬 : 싸이클이 없고 방향이 있는 그래프. 노드를 정렬해주는 알고리즘(정렬결과가 꼭 1개 X,) -> 수강신청문제
• 다익스트라 : 시작점(S)이 있고 다른 모든 노드로 가는 최단 거리를 구하는 알고리즘(단, 음수간선은 안된다)
• 벨만-포드 : 다익스트라와 같지만 음수간선도 가능하다는 차이점이 있다. 음수사이클이 있는지 판별하는 문제로 많이 나옴.
• 플로이드-워셜 : 시작점이 없고 모든 노드에 대해 최단거리를 구한다. 하지만 시간 복잡도가 좋지않다.
• 최소 신장 트리 : 모든 노드를 최소의 비용으로 연결하는 알고리즘. 사이클이 나올 수 없게끔 유니온 파인드를 사용한다.

 그래프의 표현

에지 리스트

에지 리스트는 에지를 중심으로 그래프를 표현한다. 

 

1.  에지 리스트로 가중치 없는 그래프 표현하기

가중치가 없는 그래프는 출발 노드와 도착 노드만 표현하므로 배열의 행은 2개면 충분하다.

 

☝🏻 만약 방향이 없다면 S, E를 상관하지 않고 넣는 방법을 사용하거나 (1, 2)(2, 1)이렇게 두개를 넣는 방법을 사용한다.

 

2. 에지 리스트로 가중치 있는 그래프 표현하기

가중치가 있는 그래프는 행을 3개로 늘려서 3번째 행에 가중치를 저장한다.

 

☝🏻 특정 노드와 관련되어 있는 에지를 탐색하기 어렵다. 주로 벨만 포드나 크루스칼 알고리즘에 사용한다. 노드 중심 알고리즘에서는 사용X

 

인접 행렬

인접행렬은 2차원 배열을 자료구조로 이용하여 그래프를 표현한다.

N = [N] X [N] ( 예를 들어 노드가 5개라면 5 X 5 행렬을 사용 )

 

1.  인접 행렬로 가중치 없는 그래프 표현하기

☝🏻 1에서 2로 향하는 에지를 인접행렬은 1행 2열에 1을 저장하는 방식으로 표현한다.

 

2. 인접 행렬로 가중치가 있는 그래프 표현하기

☝🏻 가중치 없는 그래프에서 1을 저장했던 것을 가중치로 바꿔서 저장한다.

 

💡  인접 행렬의 문제점

인접 행렬을 이용한 그래프는 구현이 쉽다.

하지만 노드와 관련되어 있는 에지를 탐색하려면 N번 접근해야 하므로 노드 개수에 비해 에지가 적은 경우에는 공간 효율성이 떨어진다. 

또한 노드 개수가 많을 경우에는 배열 자체를 선언불가한 경우도 있다. ex) 노드가 3만개가 넘으면 자바 힙 스페이스 에러가 발생한다.

* 힙 스페이스 에러 : heap 영역의 공간이 부족해서 생기는 오류

 

☝🏻 따라서, 인접 행렬은 노드 개수에 따라 사용 여부를 적절하게 판단하는 능력이 있어야한다. 

 

 

인접 리스트 ⭐️⭐️⭐️

 

노드 개수만큼 ArrayList를 선언하여 그래프를 표현한다.

 

1.  인접 리스트로 가중치 없는 그래프 표현하기

자료형을 판단해서 ArrayList<자료형>[]와 같이 ArrayList배열로 선언한다.

A[3].add(4)

 

2. 인접 리스트로 가중치 있는 그래프 표현하기

자료형을 판단해서 ArrayList<Node>[]와 같이 ArrayList배열로 선언한다.

Node는 class를 사용해서 만든 객체(E : 끝노드, V : 가중치) -> 구현해야함

A[3].add(new Node(4, 13))

 

💡  인접 리스트 사용 이유

인접 리스트는 그래프 구현이 복잡하다. 그럼에도 사용하는 이유는

1. 노드와 연결되어있는 에지를 탐색하는 시간이 매우 효율적이다.
2. 노드 개수가 커도 공간 효율이 좋아 메모리 초과 에러를 방지할 수 있다.

 

 1707 : 이분 그래프

문제

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

 

입력

입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호 u, v (u ≠ v)가 빈 칸을 사이에 두고 주어진다. 

• 2 ≤ K ≤ 5
• 1 ≤ V ≤ 20,000
• 1 ≤ E ≤ 200,000
  
  

 

출력

K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.

입력	출력
2 3 2 1 3 2 3 4 4 1 2 2 3 3 4 4 2	YES NO

 

문제 풀이

• 노드의 집합을 2개로 나누는데 인접한 노드끼리 같은 집합이 되지 않도록 임의로 분할
• 사이클이 발생하지 않으면 무조건 이분그래프이다. 사이클이 발생했을 때는 이분 그래프가 불가능할 때가 있다.
• 이미 갔던 노드를 판별하는 DFS, BFS중 DFS를 사용한다. 만약 이미 갔던 노드를 판별할때 시작 노드와 같은 집합인지 판단한다.

💡  순서

 

1. 입력된 그래프 데이터를 인접 리스트로 구현한다.
   
   
2. 모든 노드로 각각 DFS 탐색 알고리즘을 적용해 탐색을 수행한다.
   DFS를 실행할 때 현재 노드에서 연결된 노드 중 이미 방문한 노드가 나와 같은 집합이면 이분 그래프가 아닌 것으로 판별한다.
   실행 결과가 이분 그래프가 아니면 이후 노드는 탐색하지 않는다. 

 

실행 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.StringTokenizer;

public class P1707_BipartiteGraph {
    static ArrayList<Integer>[] A;
    static int[] check;
    static boolean[] visited;
    static boolean IsEven;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());

        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            int V = Integer.parseInt(st.nextToken()); //노드
            int E = Integer.parseInt(st.nextToken()); //간선

            // 인접리스트 & 체크 & 방문여부 & 이분그래프 여부
            A = new ArrayList[V+1];
            for(int j=1;j<=V;j++){
                A[j] = new ArrayList<Integer>();
            }
            check = new int[V+1]; // 이분그래프 집합 표현 (0, 1)
            visited = new boolean[V+1]; // 방문 여부 체크 배열
            IsEven = true;

            //인접리스트 데이터 삽입
            for(int j=0;j<E;j++){
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                A[a].add(b);
                A[b].add(a);
            }

            //모든 노드에서 DFS 실행
            for(int j=1;j<=V;j++){
                if(IsEven){
                    DFS(j);
                }else{
                    // 이분그래프가 아닌게 하나라도 있으면 이분그래프가 아닌것ㅇ으로 판단
                    break;
                }
            }
            if(IsEven) System.out.println("YES");
            else System.out.println("NO");
        }
    }

    private static void DFS(int start) {
        visited[start] = true; //방문한 노드를 체크
        for(int i : A[start]){ //인접리스트 : start에 연결된 모든 노드 탐색
            if(!visited[i]){
                //바로 직전 노드와 다른 집합으로 분류(0, 1)
                check[i] = (check[start] + 1) % 2;
                DFS(i); //재귀
            }else if(check[start] == check[i]){ //만약 방문한 노드인데 시작과 같은 집합일 경우
                IsEven = false; //이분그래프 아님
            }
        }
    }
}

 

미친거 개어려움