📙[Algo] 24.08.02 알고리즘

알고리즘 문제) BOJ 2458. 키 순서

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

문제 요약

• 1번~N번의 학생들이 존재
• N명의 학생들은 모두 키가 다름
• 학생들의 키를 비교한 결과가 주어질 때 자신의 키가 몇 번째인지 알 수 있는 학생은 모두 몇 명일까?

시간 제한

• 1초

입력

• 학생들의 수 N, 두 학생 키를 비교한 횟수 M
  • 2 ≤ N ≤ 500
  • 0 ≤ M ≤ N*(N-1)/2
• 다음 M개의 각 줄에는 두 학생의 키를 비교한 결과를 나타내는 a b가 주어짐
  • a가 b보다 키가 작다를 의미

출력

• 자신이 키가 몇 번째인지 알 수 있는 학생이 모두 몇 명인지를 출력

접근법

• 키가 몇 번째인지 알 수 있다는 의미를 그래프 관점에서 다시 해석해보자면(유방향 그래프)
  • 나를 제외한 다른노드와 연결되어있는지 파악하면 된다.
  • 즉, 내가 이동이 불가능한 노드들은 모두 나에게 이동이 가능해야한다.
• 모든 정점간의 거리를 파악할 수 있는 플로이드워셜 알고리즘을 통해, 그래프를 재구성했다.
  • 여기서 사용할 그래프는 i번째 노드보다 j번째 노드가 클 경우 arr[i][j]에 1, 자기자신은 0, 나머지는 INF값으로 초기화했다.
  • 이후, 플로이드 워셜 알고리즘을 통해 각 정점마다 다른 정점으로 이동가능한 최소 경로 값으로 갱신했다.
• 이후, 그래프를 살펴보면, 나보다 큰 애들은 INF가아닌 양수값으로 표시가 되고,
  • arr[i][j]가 INF인 경우는 아래 2가지 케이스가 존재하게 된다.
    • 파악이 불가능
    • 나보다 작은 애들
  • 위 2가지를 구분할 수 있는 방법은 arr[j][i]도 INF값일 경우 서로 이동이 불가능한 정점이라는 뜻이므로 파악이 불가능한 것이고, INF가 아닌 양수값일 경우 j노드가 i노드보다 작다는 게 확실하다는 의미다.
• 따라서 최종 arr배열에서 2중 for문으로 탐색하며 arr[i][j]도 INF, arr[j][i]도 INF인 경우를 제외하고 카운트를 해줬다.

코드

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

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

    static void floyd() {
        for (int k = 0; k < N; k++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    arr[i][j] = Math.min(arr[i][j], arr[i][k] + arr[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());
        M = Integer.parseInt(st.nextToken());

        arr = new int[N][N];

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

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

            // a가 b보다 작다
            arr[a][b] = 1;
        }

        floyd();

        boolean flag;
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            flag = true;
            for (int j = 0; j < N; j++) {
                if (arr[i][j] == INF && arr[j][i] == INF) {
                    flag = false;
                    break;
                }
            }
            if (flag) cnt++;
        }

        System.out.println(cnt);
    }
}

 

알고리즘 문제) BOJ 10159. 저울

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

문제 요약

• 무게가 서로 다른 N개의 물건이 존재
• 이때, 물건 쌍의 무게 비교 결과가 주어졌을 때, 각 물건에 대해 비교 결과를 정확히 알 수 없는 물건 개수를 출력

시간 제한

• 1초

입력

• 물건 개수 N
  • 5 ≤ N ≤ 100
• 미리 측정된 물건 쌍의 개수 M
  • 0 ≤ M ≤ 2000
• M개의 줄에 미리 측정된 비교 결과가 하나씩 주어진다
  • a b : a가 b보다 무겁다

출력

• N개의 줄에 걸쳐서 i번째 줄에 물건 i와 비교 결과를 알 수 없는 물건 개수를 출력

코드

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

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

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

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

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

            arr[a][b] = 1;
        }

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

        StringBuilder sb = new StringBuilder();
        int cnt;
        for (int i = 0; i < N; i++) {
            cnt = 0;
            for (int j = 0; j < N; j++) {
                if (arr[i][j] == INF && arr[j][i] == INF) cnt++;
            }

            sb.append(cnt).append("\n");
        }
        System.out.println(sb);
    }
}