[알고리즘] 그래프

그래프의 표현

백준 18352번

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

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 {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); // 도시의 개수
        M = Integer.parseInt(st.nextToken()); // 도로의 개수
        K = Integer.parseInt(st.nextToken()); // 거리 정보
        X = Integer.parseInt(st.nextToken()); // 출발 도시의 번호
        A = new ArrayList[N+1];
        answer = new ArrayList<Integer>();
        
        for (int i = 1; i <= N ; i++) { // N의 개수만큼 반복하기
            A[i] = new ArrayList<Integer>(); // A 인접 리스트의 각 ArrayList 초기화
        }
        
        for (int i = 0; i < M; i++) { // M의 개수만큼 반복하기
            st = new StringTokenizer(br.readLine());
            int S = Integer.parseInt(st.nextToken());
            int E = Integer.parseInt(st.nextToken());
            A[S].add(E); // A 인접 리스트에 그래프 데이터 저장하기
        }
        
        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);
            }
        }
    }
    // BFS 구현하기
    private static void BFS(int Node) {
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(Node); // 큐 자료구조에 출발 노드 더하기
        visited[Node]++; // visited 배열에 현재 노드 방문 기록하기
        while (!queue.isEmpty()) { // 큐가 빌 때까지
            int now_Node = queue.poll(); // 큐에서 노드 데이터를 가져오기
            for (int i : A[now_Node]) {
                if (visited[i] == -1) { // 현재 노드의 연결 노드 중 방문하지 않은 노드로
                    visited[i] = visited[now_Node] + 1;
                    // 큐에 데이터 삽입(add 연산)하고 visited 배열에 방문 거리 기록하기
                    queue.add(i);
                }
            }
        }
    }
}

- for문의 범위 설정하는 거랑 BFS 구성하는게 아직 생각하기 어려운 것 같다. 복습할 때 꼭 다시 풀어보기!

---

유니온 파인드

백준 1717번

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

public class Main {
    static int parent[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); // 원소 개수
        int M = Integer.parseInt(st.nextToken()); // 질의 개수
        parent = new int[N+1]; // 대표 노드 저장 배열

        for (int i = 0; i < N+1; i++) { // 대표 노드 초기화
            parent[i] = i;
        }

        for (int i = 0; i < M; i++) { // 질의 계산하는 부분
            st = new StringTokenizer(br.readLine());
            int question = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            if (question == 0) { // union
                union(a, b);
            } else { // 두 원소 같은지 보기
                boolean result = checkSame(a, b);
                if (result) {
                    System.out.println("YES");
                } else {
                    System.out.println("NO");
                }
            }
        }
    }
    private static void union(int a, int b) {
        // 대표 노드를 찾아서 연결하기
        a = find(a);
        b = find(b);
        if (a != b) {
            parent[b] = a; // 두 노드를 연결함.
        }
    }

    private static int find(int a) {
        if (a == parent[a]) { // 인덱스의 값과 value의 값이 같으면 대표 노드
            return a;
        } else { // 다르면 대표 노드를 찾아가야됨
            return parent[a] = find(parent[a]); // value를 index로 바꿔서 또 찾아보기
            // a의 대표 노드값을 parent[a]에 새로 저장해줌
            // -> 대표 노드에 도달했을 때 재귀 함수를 빠져나오면서 거치는 모든 노드값을 루트 노드값으로 변경함.
        }
    }

    private static boolean checkSame(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) {
            return true;
        }
        return false;
    }
}

- 중요한 로직은

1) union에서 대표 노드를 찾아서 연결해주기.

2) find에서 재귀함수를 이용해서 대표 노드에 도달하고 빠져나올 때 parent[a] 에 담아서 모든 노드값을 루트 노드값으로 변경해주기. -> find의 경로압축

유니온 파인드는 실제로 구현해보니까 이해하기 편했다. 그래도 반복해서 풀어보기!

---

위상정렬

백준 2252번

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); // 노드 개수
        int M = Integer.parseInt(st.nextToken()); // 에지 개수 (키를 비교한 횟수)
        ArrayList<ArrayList<Integer>> A = new ArrayList<>();
        for(int i = 0; i <= N; i++) { // 학생 수만큼 인접 리스트 초기화하기
            A.add(new ArrayList<>());
        }
        int indegree[] = new int[N+1]; // 진입 차수 배열 생성하고 초기화하기

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int S = Integer.parseInt(st.nextToken());
            int E = Integer.parseInt(st.nextToken());
            A.get(S).add(E);
            indegree[E]++; // 진입 차수 배열에 데이터 저장하기
        }

        // 위상 정렬 수행하기
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= N; i++) {
            if (indegree[i] == 0) {
                queue.offer(i); // 진입 차수 배열의 값이 0인 학생(노드)을 큐에 삽입하기
            }
        }
        while (!queue.isEmpty()) { // 큐가 빌 때까지
            int now = queue.poll();
            System.out.print(now + " "); // 현재 노드 값 출력하기
            for(int next : A.get(now)) { // 현재 노드에서 갈 수 있는 노드의 개수
                indegree[next]--; // 타깃 노드 진입 차수 배열 --
                if (indegree[next] == 0) { // 타깃 노드의 진입 차수가 0이면
                    queue.offer(next); // 큐에 타깃 노드 추가하기
                }
            }
        }

    }
}

- 위상 정렬 시작 전 인접 리스트와 진입 차수 배열을 초기화해줘야한다.

- 위상 정렬을 시작할 때는 1부터 시작한다. 

- 위상 정렬은 항상 유일한 값으로 정렬되지 않기 때문에 답이 바뀔 수 있다. 

- 여러 번 다시 풀어보면서 감 익히기!

---

다익스트라

백준 1753번

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

public class Main {

    static class Node{
        int v; //간선
        int cost; //가중치

        public Node(int v, int cost) {
            this.v = v;
            this.cost = cost;
        }
    }

    //각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트
    static ArrayList<Node>[] graph;
    //방문한 적이 있는지 체크하는 목적의 리스트
    static boolean[] visit;
    //최단 거리 테이블
    static int[] dist;

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

        int v = Integer.parseInt(st.nextToken());
        int e = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(br.readLine());

        graph = new ArrayList[v + 1];
        dist = new int[v + 1];
        visit = new boolean[v + 1];

        for (int i = 1; i <= v; i++) {
            graph[i] = new ArrayList<>();
            dist[i] = Integer.MAX_VALUE; //최대값으로 초기화, 최단거리를 찾기 위함.
        }

        for (int i = 0; i < e; i++) {
            // u -> v 로 가는 가중치 w가 주어진다.
            st = new StringTokenizer(br.readLine());
            int inputU = Integer.parseInt(st.nextToken());
            int inputV = Integer.parseInt(st.nextToken());
            int inputW = Integer.parseInt(st.nextToken());

            graph[inputU].add(new Node(inputV, inputW));
        }

        //다익스트라 알고리즘 수행
        dijkstra(k);

        for (int i = 1; i <= v; i++) {
            System.out.println(dist[i] == Integer.MAX_VALUE ? "INF" : dist[i]);
        }
    }

    static void dijkstra(int start) {
        //우선 순위 큐 사용, 가중치를 기준으로 오름차순한다.
        PriorityQueue<Node> q = new PriorityQueue<>((o1, o2) -> o1.cost - o2.cost);
        //시작 노드에 대해서 초기화
        q.add(new Node(start, 0));
        dist[start] = 0;

        while (!q.isEmpty()) {
            //현재 최단 거리가 가장 짧은 노드를 꺼내서 방문 처리 한다.
            Node now = q.poll();

            if (!visit[now.v]) {
                visit[now.v] = true;
            }

            for (Node next : graph[now.v]) {

                //방문하지 않았고, 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧을 경우
                if (!visit[next.v] && dist[next.v] > now.cost + next.cost) {
                    dist[next.v] = now.cost + next.cost;
                    q.add(new Node(next.v, dist[next.v]));
                }
            }
        }
    }
}

다익스트라 알고리즘(Dijkstra Algorithm) - JAVA

---

벨만-포드

백준 11657번

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    static Edge[] graph;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stk = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(stk.nextToken()); // 노드 개수
        int m = Integer.parseInt(stk.nextToken()); // 엣지 개수
        graph = new Edge[m + 1];
        long[] dist = new long[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);

        for (int i = 0; i < m; i++) {
            stk = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(stk.nextToken());
            int b = Integer.parseInt(stk.nextToken());
            int w = Integer.parseInt(stk.nextToken());
            graph[i] = new Edge(a, b, w);
        }

        // 벨만 - 포드 알고리즘 O(VE)
        dist[1] = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < m; j++) {
                Edge now_edge = graph[j];
                if (dist[now_edge.st] != Integer.MAX_VALUE &&
                        dist[now_edge.end] > dist[now_edge.st] + now_edge.cost) {
                    dist[now_edge.end] = dist[now_edge.st] + now_edge.cost; // update
                }
            }
        }
        // 음수 사이클 판별하기
        boolean cycle = false;
        for(int i = 0 ; i < m; i++){
            Edge now_edge = graph[i];
            if (dist[now_edge.st] != Integer.MAX_VALUE &&
                    dist[now_edge.end] > dist[now_edge.st] + now_edge.cost) {
                cycle = true;
            }
        }
        if(cycle){
            // 음수 사이클이 존재하면
            bw.write("-1\n");
        } else {
            // 음수 사이클이 존재하지 않으면
            for(int i = 2; i <= n; i++){
                if(dist[i]==Integer.MAX_VALUE)
                    bw.write(-1+"\n");
                else bw.write(dist[i]+"\n");
            }
        }
        bw.flush();
        bw.close();
    }

    static class Edge {
        int st;
        int end;
        int cost;

        public Edge(int s, int e, int c) {
            this.st = s;
            this.end = e;
            this.cost = c;
        }
    }
}

---

플로이드-워셜

백준 11404번

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
    static final int INF = 987654321;
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
 
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        int[][] arr = new int[N + 1][N + 1];
 
        // 초기값 설정
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                arr[i][j] = INF;
 
                if (i == j) {
                    arr[i][j] = 0;
                }
            }
        }
 
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            
            // 출발 도시와 도착 도시가 같지만 시간이 다른 입력값이 들어올 수 있음.
            // 예를 들어 "1 4 1"과 "1 4 2"가 입력으로 들어왔으면,
            // "1 4 1"을 택해야 함.
            arr[a][b] = Math.min(arr[a][b], c); 
        }
 
        // 플로이드 와샬 알고리즘
        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    // 최단경로 초기화
                    if (arr[i][j] > arr[i][k] + arr[k][j]) {
                        arr[i][j] = arr[i][k] + arr[k][j];
                    }
                }
            }
        }
 
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                // 갈 수 없는 곳은 0으로 초기화
                if (arr[i][j] == INF) {
                    arr[i][j] = 0;
                }
 
                sb.append(arr[i][j] + " ");
            }
            sb.append("\n");
        }
 
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
 
}

---

최소 신장 트리

백준 1197번

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

class node implements Comparable<node>{
   int s, e, v;

   public node(int s, int e, int v) {
      super();
      this.s = s;
      this.e = e;
      this.v = v;
   }

   // 간선의 크기로 오름차순하기 위한 compareTo()메서드 
   @Override
   public int compareTo(node o) {
      return this.v - o.v;
   }
   
}

public class BOJ_1197 {

   static int E, V, sum;
   static int[] parent;
   static List<node> list = new ArrayList();
   public static void main(String[] args) throws NumberFormatException, IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      
      StringTokenizer st = new StringTokenizer(br.readLine());
      E = Integer.parseInt(st.nextToken());
      V = Integer.parseInt(st.nextToken());

      parent = new int[E + 1];

      for (int i = 0; i < parent.length; i++) {
         parent[i] = i;
      }

      for (int i = 0; i < V; i++) {
         st = new StringTokenizer(br.readLine());
         int s = Integer.parseInt(st.nextToken());
         int e = Integer.parseInt(st.nextToken());
         int v = Integer.parseInt(st.nextToken());
         list.add(new node(s,e,v));
      }
      
      // 1. 간선의 크기로 오름차순 정렬
      Collections.sort(list);
      
      int size = list.size();
      // 2. 정렬된 순서대로 간선 탐색
      for (int i = 0; i < size; i++) {
         node n = list.get(i);
         // 만약 두 노드의 부모가 다르다면
         if(!isSameParent(n.s, n.e)) {
            // sum에 간선 크기 저장
            sum+=n.v;
            // 두 노드 연결
            union(n.s,n.e);
         }
         
      }
   
      System.out.println(sum);

   }

   // 간선 연결
   private static void union(int a, int b) {
      a = find(a);
      b = find(b);

      if (a != b) {
         parent[b] = a;
      }
   }

   // 부모 노드 찾기
   private static int find(int a) {
      if (parent[a] == a) {
         return a;
      }
      return parent[a] = find(parent[a]);
   }

   // 부모가 같은지를 판별해주는 method
   private static boolean isSameParent(int a, int b) {
      a = find(a);
      b = find(b);

      if (a == b)
         return true;
      else
         return false;
   }

}

복습할 때

- 크루스칼 알고리즘과 프림 알고리즘에 대해서 추가로 공부하기