[Coding Test] inflearn(11)

0. 그래프의 표현

• 노드(정점) : 정점, 무엇이든 표시할 수 있다.
  
• 에지(간선) : 노드 간 연결선
  

그래프를 구현하는 3가지 방법이 있다

1. 에지 리스트

• 에지를 중심으로 그래프를 표현
• 배열에 출발 노드, 도착 노드를 저장하여 에지를 표현 또는 출발 노드, 도착 노드, 가중치를 저장하여 가중치가 있는 에지를 표현

특징

• 구현하기 쉽다.
• 특정 노드와 관련되어 있는 에지를 탐색하기는 쉽지않다.
• 벨만 포드나 크루스칼(MST)알고리즘에 사용, 노드 중심 알고리즘에는 잘 사용하지 않는다.

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

• 가중치가 없는 그래프는 출발 노드와 도착 노드만 표현한다.
• 배열의 열 2개로 구성한다.
• 노드는 여러 자료형 사용 가능

• 방향이 있는 그래프 예시
  

  방향이 없는 그래프라면 [1,2]와 [2,1]은 같은 표현일 것이다.

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

• 가중치가 있는 그래프는 열을 3개로 늘려 3번째 열에 가중치를 저장한다.
  ex) 1에서 2로 향하는 가중치가 8인 에지는 [1,2,8]로 표현
  

2. 인접 행렬

인접 행렬은 2차원 배열을 자료구조로 이용하여 그래프를 표현한다. 인접 행렬은 에지리시트와 다르게 노드 중심으로 그래프를 표현한다.

특징

• 구현하기 쉬움

• 두 노드를 연결하는 에지의 여부와 가중치값을 배열에 직접 접근하면 바로 확인할 수 있음

• 노드와 관련되어있는 에지를 탐색하려면 N번 접근해야하므로 노드 개수에 비해 에지가 적을 때는 공간 효율이 떨어짐

• 노드 개수가 많은 경우 아예 2차원 배열 선언 자체를 할 수 없는 결함도 있다.
  -> 인접 행렬은 노드 개수에 따라 사용 여부를 적절히 판단해야한다.
  ex) 노드가 3만개 넘으면 자바 힙 스페이스 에러가 발생!

인접 행렬로 가중치 없는 그래프 표현

• 1에서 2로 향하는 에지를 1행 2열에 1을 저장하는 방식으로 표현
• 1을 저장하는 이뉴는 가중치가 없기 떄문

인접 행렬로 가중치 있는 그래프 표한

• 2에서 5로 향하는 에지를 2행 5열에 15를 저장하는 방식으로 표현

3. 인접 리스트

• 인접 리스트는 ArrayList로 그래프를 표현한다.
• 노드 개수만큼 ArrayList를 선언한다.
• 자료형은 경우에 맞게 사용한다.

특징

• 다른 방법에 비해 구현이 복잡한 편
• 노드과 연결되어 있는 에지를 탐색하는 시간은 매우 뛰어나다.
• 노드 개수가 커도 공간 효율이 좋아 메모리 초과 에러도 발생하지 않는다.
• 여러 장점으로 실제 코딩테스트에서는 인접 리스트를 이용한 그래프 구현을 선호한다.

인럽 리스트로 가중치 없는 그래프 표현

• N번 노드와 연결되어 있는 노드를 배열의 위치 N에 연결된 노드 개수만큼 배열을 연결하는 방식으로 표현

노드1과 연결된 노드 2,3은 ArrayList[1]에 [2,3]을 연결한다.

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

• 가중치가 있는 경우 자료형을 Node클래스를 선언하여 ArrayList에 사용한다.

그림을 보면, ArrayList[1]에 [(2,8),(3,3)]이 연결되어있다.
-> 노드1과 2가 가중치 8에지로, 노드 1과 3이 가중치 3에지로 연결되어있다는 뜻

4. 그래프 실전 문제

이분 그래프 (백준 1707) - 인접 리스트 & DFS

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

public class P1707_이분그래프 {
    static ArrayList<Integer>[] al;
    static boolean[] visited;
    static int[] check;
    static boolean isEven;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int K = Integer.parseInt(st.nextToken());
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            int V = Integer.parseInt(st.nextToken());
            int E = Integer.parseInt(st.nextToken());
            al = new ArrayList[V + 1];
            visited = new boolean[V + 1];
            check = new int[V + 1];
            isEven = true;
            for (int j = 1; j <= V; j++) al[j] = new ArrayList<Integer>();
            for (int j = 0; j < E; j++) {
                st = new StringTokenizer(br.readLine());
                int s = Integer.parseInt(st.nextToken());
                int e = Integer.parseInt(st.nextToken());
                al[s].add(e);
                al[e].add(s);
            }
            for (int j = 1; j <= V; j++) {
                if (isEven) DFS(j);
                else break;
            }

            if (isEven) System.out.println("YES");
            else System.out.println("NO");
        }
    }

    public static void DFS(int node) {
        visited[node] = true;
        for (int i : al[node]) {
            if (!visited[i]) {
                check[i] = (check[node] + 1) % 2;
                DFS(i);
            } else {
                if (check[node] == check[i]) {
                    isEven = false;
                }
            }
        }
    }
}