[BOJ] 21278 - 호석이 두 마리 치킨 (Python, JavaScript)

 

 

아이디어

 

플로이드-워셜 알고리즘으로 모든 건물 간 거리를 구한 후, 왕복 시간을 최소로 하는 두 건물의 조합을 찾는다.

 

 

풀이 #1 (Python)

 

건물 개수 N은 100 이하이므로 모든 건물 간 거리를 저장하는 2차원 리스트 D를 생성하여 100으로 채운다.

같은 건물 간 거리는 0으로 저장하고, 입력 받은 도로 정보를 D에 반영한다.

 

플로이드-워셜로 건물 i에서 j로 가는 시간을 건물 k를 경유하여 가는 시간과 비교해 최솟값으로 갱신해 나간다.

양방향 도로이므로 건물 j에서 건물 i에서 가는 시간도 같은 값으로 저장하며, j는 i보다 큰 번호부터 시작하도록 한다.

 

모든 건물 간 거리를 구한 후, 이중 for문에서 건물 i와 j를 선택했을 때의 왕복 시간 합을 구해 결과값을 갱신한다.

 

import sys

input = sys.stdin.readline

def solution():
    N, M = map(int, input().split())
    D = [[100]*(N+1) for _ in range(N+1)]
    for i in range(1, N+1):
        D[i][i] = 0
    for _ in range(M):
        a, b = map(int, input().split())
        D[a][b] = 1
        D[b][a] = 1
    for k in range(1, N+1):
        for i in range(1, N+1):
            if i == k:
                continue
            for j in range(i+1, N+1):
                if j == k:
                    continue
                D[i][j] = D[j][i] = min(D[i][j], D[i][k]+D[k][j])
    res = [N+1, N+1, 100*N]
    for i in range(1, N+1):
        for j in range(i+1, N+1):
            temp = 0
            for k in range(1, N+1):
                temp += min(D[i][k], D[j][k])
                if temp >= res[2]:
                    break
            else:
                if temp*2 < res[2]:
                    res = [i, j, temp*2]
    print(*res)

solution()

 

 

 

풀이 #2 (JavaScript)

 

풀이 #1과 같은 방식으로 동작하며, Array.from과 fill 메서드를 이용해 100으로 채워진 2차원 리스트 D를 생성한다.

 

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

let [N, M] = input[0].split(' ').map(Number);
let D = Array.from(Array(N+1), () => Array(N+1).fill(100));
for (let i=1; i<N+1; i++) D[i][i] = 0;
for (let i=1; i<M+1; i++) {
    let [a, b] = input[i].split(' ').map(Number);
    D[a][b] = 1;
    D[b][a] = 1;
}
for (let k=1; k<N+1; k++) {
    for (let i=1; i<N+1; i++) {
        if (i === k) continue;
        for (let j=1; j<N+1; j++) {
            if (j === k) continue;
            D[i][j] = D[j][i] = Math.min(D[i][j], D[i][k]+D[k][j]);
        }
    }
}
let res = [N+1, N+1, 100*N];
for (let i=1; i<N+1; i++) {
    for (let j=1; j<N+1; j++) {
        let temp = 0;
        for (let k=1; k<N+1; k++) {
            temp += Math.min(D[i][k], D[j][k]);
            if (temp >= res[2]) break;
        }
        if (temp*2 < res[2]) res = [i, j, temp*2];
    }
}
console.log(...res);