[알고리즘] 백준 10159 저울 -플로이드 워셜- 자바 코틀린

 

 

www.acmicpc.net/problem/10159

10159번: 저울

 

 

 

 

백준 플로이드 워셜에서 간단한게 복습겸 정답률 괜찮은 문제를 골라 풀어봤습니다. ㅎㅎ

그러나 정답률은 60퍼인데 플로이드 워셜로 어떻게 풀지 생각이 잘 안나고 애를 먹은 문제였습니다. 후..(solved.ac 티어도 봤는데 저한텐 아직 어려운 골3 문제였습니다. ㅠ ) 이전 플로이드 문제들에서 플로이드 알고리즘 사용시 Math.min() 에 너무 익숙해져서 시야가 좁아진 것도 한몫 했다고 봅니다.

 

 

플로이드 워셜의 특징 중 하나인 3중 for문으로 모든 물건들의 무게를 비교할 수 있다는 점을 사용하면 됩니다. 

 

주석으로 풀이를 자세하게 적어놨습니다. 

 

풀이는 다음과 같습니다.

 

[Java]

import java.util.Scanner;

class Main {
    private static int N; // N개의 물건
    private static int M; // 미리 측정된 물건쌍의 개수
    private static int[][] weights;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        weights = new int[N + 1][N + 1];
        // 무게 대소관계 정리
        for (int i = 1; i <= M; i++) {
            int start = sc.nextInt(); // 더 무거운 물건
            int end = sc.nextInt(); // 더 가벼운 물건
            weights[start][end] = 1; // 처음물건이 두번쨰물건모다 무겁다. 처음께(1차원배열) 두번째(2차원배열)보다 무거우면 1 세팅
            weights[end][start] = -1; // 반대의 경우는 -1 세팅
            // 대소관계모르는 경우 0
        }
        floyd();
        for (int i = 1; i <= N; i++) {
            int cnt = N - 1; //자기자신 제외
            for (int j = 1; j <= N; j++) {
                if (weights[i][j] != 0) { //대소관계 모르는 경우
                    cnt--;
                }
            }
            System.out.println(cnt);
        }
    }

    private static void floyd() {
        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (weights[i][k] == weights[k][j] && weights[i][k] != 0) { //서로 비교할 수 있는 경우
                        weights[i][j] = weights[i][k]; // i>k>j OR i<k<j 이므로 i,k 의 대소관계도 알 수 있게된다.
                    }
                }
            }
        }
    }
}

 

 

[Kotlin]

import java.util.*

private var N // N개의 물건
        = 0
private var M // 미리 측정된 물건쌍의 개수
        = 0
private lateinit var weights: Array<IntArray>

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    N = sc.nextInt()
    M = sc.nextInt()
    weights = Array(N + 1) { IntArray(N + 1) }
    // 무게 대소관계 정리
    for (i in 1..M) {
        val start = sc.nextInt() // 더 무거운 물건
        val end = sc.nextInt() // 더 가벼운 물건
        weights[start][end] = 1 // 처음물건이 두번쨰물건모다 무겁다. 처음께(1차원배열) 두번째(2차원배열)보다 무거우면 1 세팅
        weights[end][start] = -1 // 반대의 경우는 -1 세팅
        // 대소관계모르는 경우 0
    }
    floyd()
    for (i in 1..N) {
        var cnt = N - 1 //자기자신 제외
        for (j in 1..N) {
            if (weights[i][j] != 0) { //대소관계 모르는 경우
                cnt--
            }
        }
        println(cnt)
    }
}

fun floyd() {
    for (k in 1..N) {
        for (i in 1..N) {
            for (j in 1..N) {
                if (weights[i][k] == weights[k][j] && weights[i][k] != 0) { //서로 비교할 수 있는 경우
                    weights[i][j] = weights[i][k] // i>k>j OR i<k<j 이므로 i,k 의 대소관계도 알 수 있게된다.
                }
            }
        }
    }
}

댓글과 공감은 큰 힘이 됩니다. 감사합니다 !!!