[PS | 한번에 맞자!] 백준 21278

0. 에필로그
원래 백준 문제는 블로그에 안 쓰고 개인적으로 정리했는데 코알라 면접 보다가 큰 영감을 얻어 열심히 기록해볼 생각이다! 👻 일주일에 적어도 5개는 풀어야징
1. 문제
https://www.acmicpc.net/problem/21278

21278번: 호석이 두 마리 치킨

2. 생각
"모든 건물에서 가장 가까운 치킨집까지 왕복하는 최단 시간의 총합"을 최소화할 수 있는 건물 두 개를 고르는 문제이다.
우선 이 문제에서 요구하는 현상을 2차원 그래프로 표현할 수 있을지 생각해보았고, 표현해보니 시간복잡도 상으로 가능하였다.
그리고 건물 두 개를 골라야 하니 combination으로 골라 해결하기로 하였다.
하지만 combination은 문제 출력 조건의 "만약 건물 조합이 다양하게 가능하면, 작은 번호가 더 작은 것을, 작은 번호가 같다면 큰 번호가 더 작은 걸 출력한다."에 맞지 않다고 판단하여 이후 변경하였다.
3. 실제 풀이 (종이)

4. 코드

N,M=map(int,input().split())
cost=[[float('inf') for _ in range(N+1)] for _ in range(N+1)]

for _ in range(M):
    a,b=map(int,input().split())
    cost[b][a]=1
    cost[a][b]=1

for i in range(1,N+1):
    cost[i][i]=0

for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            if cost[i][j] > cost[i][k]+cost[k][j]:
                cost[i][j] = cost[i][k]+cost[k][j]
# print(cost)
ans=float('inf')
ans_1=0; ans_2=0
arr=[i for i in range(1,N+1)]
for x in range(N):
    for y in range(x,N+1):
        # print(i)
        temp=0
        for j in range(1,N+1):
            temp+=min(cost[j][x], cost[j][y])
        if ans>temp: 
            ans_1=x; ans_2=y
            ans=temp;
# print(List)
print(ans_1, ans_2, ans*2)

5. 한 번에 풀었는가? X
한 번에 풀 수 있을 줄 알았는데 .. 플로이드 워셜 로직의 for문 변수 할당을 계속 잘못 짜고 있었다.
다음 번 플로이드 워셜 로직에서는 맨 처음 for문 부분을 실수하지 말자ㅠㅠ