[문제 풀이] 백준 1389

해결 과정

그래프 내의 최단거리만 구한다면 다음과 같은 아이디어 사용. index out of bound 에러가 나서 살펴보니 N과 M을 바꿔서 작성했거나 0번 인덱스 제외하고 푸는 부분에서 실수가 있어서 고쳤다. 

 

나의 풀이

# 9:51 - 10:43
from cmath import inf
from collections import deque


def kebinBaconNum(i, j, graph):
    visited = [False] * (len(graph) + 1)
    queue = deque([i])
    answer = 0

    while queue:
        answer += 1
        for _ in range(len(queue)):
            for g in graph[queue.popleft()]:
                if g == j:
                    return answer
                elif visited[g] == False:
                    visited[g] = True
                    queue.append(g)

    return answer


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

kebinBaconNumGraph = [[0]*(N+1) for _ in range(N+1)]

for i in range(1, N+1):
    for j in range(i+1, N+1):
        kebinBaconNumGraph[i][j] = kebinBaconNum(i, j, graph)

answer = [float(inf)]
for i in range(1, N+1):
    tmp = 0
    for j in range(1, N+1):
        if i > j:
            tmp += kebinBaconNumGraph[j][i]
        elif i < j:
            tmp += kebinBaconNumGraph[i][j]
    answer.append(tmp)

print(answer.index(min(answer)))

 

다른 풀이

 

 

IDEA