[Python][백준 21278] 호석이 두 마리 치킨

https://www.acmicpc.net/problem/21278

21278번: 호석이 두 마리 치킨

---

/*
신경써야 할 부분은 바로 :
1. 플로이드 워셜을 통해 각 건물간의 거리를 구한다.
2. 치킨집은 총 두개이고 각 치킨집에서 다른 건물까지 걸리는 시간을 비교한다
3. 더 작은 값의 2를 곱한뒤 저장한다 (왕복 소요 시간)
4. 각 치킨집의 위치를 완전탐색으로 돌리며 위의 방법으로 구한 값을 비교한다.
5. 더 작은 값의 치킨집 위치를 같이 저장한다.

플로이드 워셜을 알면 큰 무리 없이 풀 수 있는 문제인듯 하다
*/

---

import sys
input = sys.stdin.readline
 
INF = float('inf')

def floyd_warshall(graph):
    n = len(graph)
    dist = [[0 if i == j else graph[i][j] if graph[i][j] != 0 else INF for j in range(n)] for i in range(n)]
 
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    return dist

n,m = map(int, input().split())
graph = [[INF for _ in range(n+1)] for _ in range(n+1)]

for i in range(m) :
    a,b = map(int, input().split())
    
    graph[a][a] = 0
    graph[b][b] = 0
    graph[a][b] = 1
    graph[b][a] = 1

shortest_paths = floyd_warshall(graph)
    
result = [-1,-1,INF]

for i in range(1,n+1) :
    for j in range(1,n+1) :
        temp = []
        if i == j : 
            continue
        for k in range(1,n+1) :
            temp.append(min(shortest_paths[i][k]*2, shortest_paths[j][k]*2))
        
        if sum(temp) < result[2] :
            result = [i,j,sum(temp)]
        
print(" ".join(map(str,result)))

---

풀 때 어려웠던 점 또는 느낀점 :

공익 PS 6일차

문제를 꼼꼼히 읽고 이해한 뒤에 생각하니 간단한 문제였다.

골5 문제를 오랜만에 간단하게 푼거 같아 기분이 좋다

오늘도 화이팅 내일도 화이팅!!!

---

참고할만한 다른 사람 코드 :

# 21278 호석이 두 마리 치킨
# 2023-10-15

import sys
from itertools import combinations

# Infinity
INF = int(1e10)

# 건물의 개수 N, 도로의 개수 M
N, M = map(int, sys.stdin.readline().split())

# 건물
building = [i for i in range(1, N+1)]

# 2개 건물의 조합
combs = list(combinations(building, 2))

# 그래프 초기화
graph = [[INF] * (N+1) for _ in range(N+1)]

# 자기 자신은 초기화
for i in range(1, N+1):

    graph[i][i] = 0

# M개의 줄에 걸쳐 도로의 정보가 주어진다.
for _ in range(M):

    a, b = map(int ,sys.stdin.readline().split())

    # 양방향 간선, 1시간에 이동가능
    graph[a][b] = 1
    graph[b][a] = 1

# Floyd-Warshall Algorithm
for k in range(1, N+1):

    for i in range(1, N+1):

        for j in range(1, N+1):

            graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j])

# 모든 조합에 대해서 조사(조합은 오름차순 정렬)
min_total = INF
for comb in combs:

    # 치킨 집 a와 b
    a = comb[0]
    b = comb[1]

    # 거리합 누적
    total = 0

    for t in range(1, N+1):

        total += min(graph[a][t], graph[b][t])
    
    # 왕복 거리 계산
    total *= 2

    if total < min_total:

        # 최소값 갱신
        min_total = total

        # 답 갱신
        ans = [a, b, total]
        
print(*ans)

 

위의 코드도 플로이드-워셜이랑 브루트포스로 푼 듯하다

주석을 엄청 꼼꼼히 달았다. 이해하기 편해 보인다.

배울 점인것 같다.