[알고리즘] 다양한 유형의 그래프 문제들

 

 

그래프를 구현하는 방법에는 다양한 접근 방식이 있다.

 

1. 에지 리스트
: 에지를 중심으로 그래프를 표현
: 열의 갯수를 2개를 두냐, 3개를 두냐에 따라서 가중치가 유무를 표현할 수 있다.
: 벨만 포드나 크루스칼 알고리즘에 사용하며, 노드 중심 알고리즘에는 잘 사용하지 않는다.

2. 인접 행렬
: 행과 열에 그래프 정보를 저장한다.(가령, 1행 2열에 표시하는 것은 1에서 2를 향하는 에지를 나타냄)
: 가중치가 없는 경우 1을 저장하지만, 가중치가 있다면 그 값을 저장한다.

3. 인접 리스트
: ArrayList로 그래프를 표현한다.
: 가중치가 없다면, ArrayList<Integer>[5]와 같은 식으로 표현한다.
: 가중치가 있다면 각 ArrayList의 값에 노드를 두어 가중치 값을 저장할 수 있다.
: 노드 개수가 커도 공간 효율이 좋다.

 

 

 

 

 

 

이동 거리 저장하기

 

 

BFS를 통해서 이동길이를 저장하는 문제를 풀어보자.

18352번: 특정 거리의 도시 찾기

 

 

import java.nio.Buffer;
import java.util.*;
import java.io.*;

public class Main {
    static int visited[];
    static ArrayList<Integer>[] A;
    static int N, M, K, X;
    static List<Integer> answer;

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        K = sc.nextInt();
        X = sc.nextInt();

        A = new ArrayList[N+1];
        answer = new ArrayList<>();
        for(int i=1; i<=N; i++) {
            A[i] = new ArrayList<Integer>();
        }
        for(int i=0; i<M; i++) {
            int S = sc.nextInt();
            int E = sc.nextInt();

            A[S].add(E);
        }
        visited = new int[N+1];
        for(int i=0; i<=N; i++) {
            visited[i] = -1;
        }
        BFS(X);
        for(int i=0; i<=N; i++) {
            if (visited[i] == K) {
                answer.add(i);
            }
        }
        if (answer.isEmpty()) {
            System.out.println(-1);
        } else {
            Collections.sort(answer);
            for(int temp:answer) {
                System.out.println(temp);
            }
        }

    }

    private static void BFS(int Node) {
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(Node);
        visited[Node]++;
        while(!queue.isEmpty()) {
            int now_Node = queue.poll();
            for(int i : A[now_Node]) {
                if (visited[i] == -1) {
                    visited[i] = visited[now_Node] + 1;
                    queue.add(i);
                }
            }
        }
    }
}

 

- 이동 거리를 저장해주기 위해 visited[i] = visited[now_Node] + 1를 적어준다.

 

 

 

 

 

이분 그래프 구하기

 

1707번: 이분 그래프

 

import java.util.*;
import java.io.*;

public class Main {

    static boolean[] visited;
    static ArrayList<Integer>[] A;

    static boolean IsEven;
    static int[] check;



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

        // for(k만큼 반복)
        // -> v(노드 갯수), e(에지 갯수)
        // for(v의 갯수만큼 반복)
        // -> 초기화
        // for(e만큼 반복)
        // -> 그래프 데이터 저장

        for(int i=0; i<k; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int v = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());

            A = new ArrayList[v+1];
            visited = new boolean[v+1];
            check = new int[v+1];
            IsEven = true;

            for(int j=1; j<=v; j++) {
                A[j] = new ArrayList<>();
            }
            for(int j=0; j<e; j++) {
                st = new StringTokenizer(br.readLine());
                int S = Integer.parseInt(st.nextToken());
                int E = Integer.parseInt(st.nextToken());

                A[S].add(E);
                A[E].add(S);
            }
            // for(v의 개수만큼 반복)
            // -> 각 노드에서 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");
            }

        }


    }
    // DFS구현
    // if (현재 노드 중 방문하지 않은 노드로)
    // -> 현재 노드와 다른 집합으로 연결 노드 저장
    // -> DFS실행

    // else (방문한 노드인데, 같은 집합인 경우)
    // -> 이분 그래프가 아님
    public static void DFS(int Node) {
        visited[Node] = true;

        for(int i: A[Node]) {
            if (!visited[i]) {
                check[i] = (check[Node] + 1) % 2;
                DFS(i);
            } else if (check[Node] == check[i]) {
                IsEven = false;
            }
        }
    }
}

 

 

인접 요소가 같은 그룹인지 확인하기 위해서 check라는 배열을 사용한다.

 

- check[i] = (check[Node] + 1) % 2를 통해서, 새롭게 방문하는 배열이 어느 그룹에 속해있는 지 확인 할 수 있다.

 

 

 

 

그래프를 역으로 그리는 방식

 

지금까지는 그래프 데이터를 저장하고 저장한 자료구조를 이용하였다.

하지만, 이 문제는 반대로 그래프를 역으로 그리며 접근한다.

 

2251번: 물통

 

 

import java.util.*;
import java.io.*;

public class Main {
    static int[] Sender = { 0, 0, 1, 1, 2, 2 };
    static int[] Receiver = { 1, 2, 0, 2, 0, 1};
    static boolean visited[][];
    static boolean answer[];
    static int now[];

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        now = new int[3];
        now[0] = sc.nextInt();
        now[1] = sc.nextInt();
        now[2] = sc.nextInt();

        visited = new boolean[201][201];
        answer = new boolean[201];
        BFS();

        for(int i =0; i<answer.length; i++) {
            if (answer[i]) System.out.print(i + " ");
        }

    }

    public static void BFS() {
        Queue<AB> queue = new LinkedList<>();
        queue.add(new AB(0, 0));
        visited[0][0] = true;
        answer[now[2]] = true;
        while(!queue.isEmpty()) {
            AB p = queue.poll();
            int A = p.A;
            int B = p.B;
            int C = now[2] - A-B;

            for(int k = 0; k<6; k++){
                int[] next = { A, B, C };
                next[Receiver[k]] += next[Sender[k]];
                next[Sender[k]] = 0;
                if (next[Receiver[k]] > now[Receiver[k]]) {
                    next[Sender[k]] = next[Receiver[k]] - now[Receiver[k]];
                    next[Receiver[k]] = now[Receiver[k]];
                }
                if(!visited[next[0]][next[1]]) {
                    visited[next[0]][next[1]] = true;
                    queue.add(new AB(next[0], next[1]));
                    if (next[0] == 0) {
                        answer[next[2]] = true;
                    }
                }
            }

        }
    }
}

class AB {
    int A;
    int B;
    public AB (int A, int B) {
        this.A = A;
        this.B = B;
    }
}

 

 

 

- Sender와 Receiver를 통해서, 이동 케이스를 나누었다.

- visited 배열은 A,B무게만 있으면 하나는 고정되므로 2차원으로 고정하였다.

- BFS()함수 안에 queue를 구현하여 A,B 무게를 저장하고 6가지 이동 케이스를 따져가며 물을 저장하였다.

- 방문 배열을 체크하고, 부합한다면 A의 물의 양이 0일 때 정답 변수에 저장한다.

 

 

 

 

 

Reference

 

- Do it! 코딩 테스트 - 기본 편