📙[Algo] 24.08.01 알고리즘

알고리즘 문제) BOJ 1613. 역사

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

문제 요약

• 알고 있는 일부 사건들의 전후 관계들이 주어질 때, 주어진 사건들의 전후 관계를 찾아라

시간 제한

• 1초

입력

• 사건의 개수 N, 알고 있는 전후 관계 개수 K
  • N : 400이하 자연수
  • K : 4만 이하 자연수
• K개 줄에 사건의 전후 관계를 알고 있는 두 사건 번호가 주어짐
  • a b
    • a는 보다 먼저 발생
• 사건의 전후 관계를 알고 싶은 사건 쌍의 수 S
  • S : 5만 이하 자연수
• S개 줄에 서로 다른 두 사건 번호가 주어짐

출력

• S개 줄에 걸쳐
  • 앞에 있는 번호의 사건이 먼저 일어났으면 -1
  • 뒤에 있는 번호의 사건이 먼저 일어났으면 1
  • 유추할 수 없으면 0을 출력

접근법

• 처음에 위상정렬로 풀려고 했는데, 생각해보니 나중에 알고 싶은 전후 관계 개수를 파악하려면, 위상정렬로 접근하기 어렵다고 느껴졌다.
• 따라서 알고 있는 전후 관계 p c가 주어진다면
  • dist[p][c]에 1을 저장했다.
  • 즉, p가 c보다 먼저 일어난 경우에 1을 저장했고, 자기 자신은 0, 그 외에는 INF값으로 초기화 했다.
• 이후 플로이드 워셜 알고리즘을 통해
  • j사건이 i사건 이후에 발생한다는 게 확실할 경우에만
    • i사건 이후 j사건이 발생하기까지 필요한 최소 사건 수를 기록했다.
• 이후 dist배열을 조회할 경우
  • 알고 싶은 사건 i와 사건 j가 주어질 때
  • dist[i][j]가 INF 값이 아니라면,
    • 무조건 i가 j보다 먼저 일어나는 경우로 -1을 출력했고
  • INF값일 경우
    • j가 i보다 먼저 일어나는 경우가 확실하지 않다면 dist[j][i]가 INF
    • 그게 아니라면 INF가 아닌 양수값일 것이다.
    • 이를 구분해 INF값일 경우 추정 불가인 0, 그게 아닐 경우 1을 출력했다.

코드

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

public class Main {
    static int N, K, S;
    static int[][] dist;
    static final int INF = 1_000_000_010;

    static void floyd() {
        for (int k = 0; k < N; k++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }

    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());

        dist = new int[N][N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (i != j) dist[i][j] = INF;
            }
        }

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

            dist[p][c] = Math.min(dist[p][c], 1);
        }

        floyd();

        S = Integer.parseInt(br.readLine());
        int a, b;
        StringBuilder sb = new StringBuilder();
        while (S-- > 0) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken()) - 1;
            b = Integer.parseInt(st.nextToken()) - 1;

            if (dist[a][b] == INF){
                if (dist[b][a] == INF) sb.append(0);
                else sb.append(1);
            }
            else {
                sb.append(-1);
            }
            sb.append("\n");
        }

        System.out.println(sb);
    }
}

 

알고리즘 문제) BOJ 11404. 플로이드

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

문제 요약

• N개의 도시와 M개의 버스가 존재
• 출발 도시와 도착 도시의 비용에 관한 버스의 노선이 주어질 때
• 모든 도시쌍에 대해 두 도시간 이동할 때 필요 비용의 최솟값을 출력해라

시간 제한

• 1초

입력

• 도시 개수 N
  • 2 ≤ N <+ 100
• 버스 개수 M
  • 1 ≤ M ≤ 10만
• M개의 줄에 버스 노선 정보 주어진다
  • 출발 도시 a, 도착 도시 b, 비용 c
  • a ≠ b
  • c : 10만 이하 자연수
  • a와 b를 연결하는 노선은 여러 개 존재 가능

출력

• n개의 줄에
  • i번째 도시에서 j번째 도시로의 최소 비용을 출력
  • 만약 갈 수 없다면 0 출력

접근법

• 모든 정점간의 최소 비용을 구해야하므로 플로이드워셜 알고리즘 사용
• 시간 복잡도 ⇒ O(NNN) = 100100100

코드

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

public class Main {
    static int N, M;
    static int[][] graph;
    static final int INF = 1_000_000_010;

    static void floyd() {
        for (int k = 0; k < N; k++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    // i -> j로 가능 경우와
                    // i -> k -> j로 가는 경우 비교
                    // 최솟값으로 갱신
                    graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
                }
            }
        }
    }

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

        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());

        graph = new int[N][N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                // 자기 자신으로 연결되는 경우가 아닐 경우 INF로 초기화
                if (i != j) graph[i][j] = INF;
            }
        }

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

            // 도로가 여러 개 존재 가능 -> 가장 최소 경로로 갱신
            graph[a][b] = Math.min(graph[a][b], c);
        }

        floyd();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (graph[i][j] == INF) System.out.print(0 + " ");
                else System.out.print(graph[i][j] + " ");
            }
            System.out.println();
        }
    }
}