📙[Algo] 24.08.05 ~ 24.08.07 알고리즘

알고리즘 문제) BOJ 2176. 합리적인 이동경로

• 링크 : https://www.acmicpc.net/problem/2176

문제 요약

• 그래프의 한 정점 S에서 다른 한 정점 T로 이동
• 이동할 때 T에 가까워지며 이동하는 경우, 이를 합리적인 이동경로
  • 이러한 경로는 최단경로가 아닐 수도 있다
• 그래프가 주어졌을 때 가능한 합리적인 이동경로의 개수를 구하는 프로그램을 작성

시간 제한

• 2초

입력

• 첫째 줄에 정점의 개수 N(1 < N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 100,000)
• 다음 M개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C
  • A번 정점과 B번 정점이 길이 C(0 < C ≤ 10,000)인 간선으로 연결되어 있다는 의미
  • 두 정점은 최대 한 개의 간선으로만 연결
  • 간선은 방향성이 없다

출력

• 첫째 줄에 답을 출력한다.
  • 답은 2147483647을 넘지 않는다.

접근법

• 합리적인 경로라는 의미는?
  • dist(a,b) : 정점 a에서 정점 b로의 거리를 의미 한다면
  • 도착 정점을 e라고 했을 때
  • dist(v, e)가 점점 작아지는 정점을 선택하며 진행해야 한다.
    • 즉, 만약 a정점에서 b정점으로 이동하려면
      • dist(a, e) > dist(b, e)인 경우만 이동한다는 의미
• 그렇기 때문에, 가능한 경우의 수를 구하기 전에 미리 출발 정점 1번 에서 도착 정점 2번으로의 최단 경로를 구해야한다.
  • 이때, 역다익스트라를 활용하여
    • 도착정점을 출발정점으로 가정하여 다익스트라 알고리즘으로 돌렸다.
    • 즉, dist배열에는 dist[v] : 도착정점 ~ v로의 최단 거리를 의미
• 이후, 재귀 함수를 돌면서
  • 현재 정점 cur을 매개변수로 넘겨 주며
    • 그 다음 정점 nxt으로 이동할 때
      • dist[cur] > dist[nxt] 인 경우에만 이동하도록 했다.
        • dist[cur] : 현재 정점 ~ 도착 정점 거리
        • dist[nxt] : 다음 정점 ~ 도착 정점 거리
  • 도착 정점에 도착할 경우 가능한 경우의 수이므로 1을 반환시켰다.
  • 또한, 메모이제이션을 통해, 같은 정점을 또 탐색하지 않도록 최적화를 진행했다.

코드

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

public class Main {
    static int N, K;
    static ArrayList<Node>[] lst;
    static boolean[] visted;
    static PriorityQueue<Node> pq = new PriorityQueue<>();
    static int[] dist;
    static int[] dp;

    static class Node implements Comparable<Node> {
        int to;
        int cost;

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

        @Override
        public int compareTo(Node node) {
            return this.cost - node.cost;
        }
    }

    static int recur(int cur) {
        if (cur == 2) return 1;

        if (dp[cur] != -1) return dp[cur];

        int nxt, ret = 0;
        for (Node node : lst[cur]) {
            nxt = node.to;

            if (dist[cur] > dist[nxt]) {
                ret += recur(nxt);
            }
        }

        dp[cur] = ret;
        return ret;
    }

    static void daijk(int start) {
        Arrays.fill(dist, 1 << 30);
        dist[start] = 0;
        pq.offer(new Node(start, 0));

        int cur, nxt, nc;
        while (!pq.isEmpty()) {
            cur = pq.poll().to;

            if (visted[cur]) continue;

            visted[cur] = true;

            for (Node node : lst[cur]) {
                nxt = node.to;
                nc = dist[cur] + node.cost;

                if (dist[nxt] > nc) {
                    dist[nxt] = nc;
                    pq.offer(new Node(nxt, dist[nxt]));
                }
            }
        }
    }

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

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        lst = new ArrayList[N + 1];
        for (int i = 0; i < N + 1; i++) {
            lst[i] = new ArrayList<>();
        }
        visted = new boolean[N + 1];
        dist = new int[N + 1];
        dp = new int[N + 1];
        Arrays.fill(dp, -1);

        int a, b, c;
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());

            lst[a].add(new Node(b, c));
            lst[b].add(new Node(a, c));
        }

        // 역방향 다익스트라... 왜 이생각을 못했지?
        daijk(2);

        int ans = recur(1);

        System.out.println(ans);
    }
}

 

알고리즘 문제) BOJ 18223. 민준이와 마산 그리고 건우

• 링크 : https://www.acmicpc.net/problem/18223

문제 요약

• 출발지는 1번 정점, 마산은 V번 정점이 있으며, 1~V번의 정점이 존재한다.
• 이때, 건우는 P번 정점에 있다.
• 또한, 항상 1번 정점에서 P번과 V번 정점으로 갈 수 있는 경로가 존재한다.
• 이때 중복 간선과 자기 자신을 가리키는 간선은 존재하지 않는다.
• 민준이는 무조건 마산으로 가야하는데, 그때의 최단 경로위에 건우가 있다면 구해라

시간 제한

• 1초

입력

• 정점의 개수 V와 간선의 개수 E*,* 그리고 건우가 위치한 정점 P
  • 2 ≤ V  ≤ 5,000, 1 ≤ E ≤ 10,000, 1 ≤ P  ≤ V
• 두 번째 줄부터 E개의 줄에 걸쳐 각 간선의 정보 a,b,c가 공백으로 구분
  • a번 정점과 b번 정점 사이의 거리가 c임을 의미
  • 1 ≤ a,b ≤ V, 1 ≤ c  ≤ 10,000

출력

• 민준이가 찾은 최단 경로 위에 건우가 있다면 "SAVE HIM" 을 아니면 "GOOD BYE" 를 출력

접근법

• 최단 경로에 민준가 위치한 P정점이 있는지 확인하는 방법
  • “ (출발정점1 ~ P정점까지의 최단경로 길이) + (P정점 ~ 도착정점V까지의 최단 경로 길이) == (출발정점1 ~ 도착정점V까지의 길이) “인지 확인
• 최단 경로 알고리즘으로는 다익스트라를 사용

코드

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

public class Main {
    static int V, E, P;
    static ArrayList<Node>[] lst;
    static int[] dist;
    static boolean[] visited;
    static PriorityQueue<Node> pq = new PriorityQueue<>();

    static class Node implements Comparable<Node>{
        int to;
        int cost;

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

        @Override
        public int compareTo(Node node) {
            return this.cost - node.cost;
        }
    }

    static void daijk(int start) {
        pq.offer(new Node(start, 0));

        int cur, nxt, nd;
        while (!pq.isEmpty()) {
            cur = pq.poll().to;


            if (visited[cur]) continue;

            visited[cur] = true;

            if (cur == V) return;

            for (Node node : lst[cur]) {
                nxt = node.to;
                nd = dist[cur] + node.cost;

                dist[nxt] = Math.min(dist[nxt], nd);

                pq.offer(new Node(nxt, dist[nxt]));
            }
        }
    }


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

        st = new StringTokenizer(br.readLine());
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        P = Integer.parseInt(st.nextToken());

        lst = new ArrayList[V + 1];
        for (int i = 0; i < V + 1; i++) {
            lst[i] = new ArrayList<>();
        }

        int a, b, c;
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());

            lst[a].add(new Node(b, c));
            lst[b].add(new Node(a, c));
        }

        dist = new int[V + 1];
        visited = new boolean[V + 1];

        Arrays.fill(dist, 1 << 30);
        dist[1] = 0;
        daijk(1);
        int dist1 = dist[V];
        int dist2 = dist[P];

        Arrays.fill(visited, false);
        Arrays.fill(dist, 1 << 30);
        dist[P] = 0;
        daijk(P);
        int dist3 = dist[V];

        if (dist1 == dist2 + dist3) {
            System.out.println("SAVE HIM");
        } else {
            System.out.println("GOOD BYE");
        }
    }
}