문제

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

소스코드

import sys
input = sys.stdin.readline

if __name__ == "__main__":  
    n,m = map(int,input().split())
    tree = [[] for _ in range(n+1)]
    #트리 생성
    for _ in range(m):
        a,b = map(int,input().split())
        tree[a].append(b)
        tree[b].append(a)
    #치킨집을 임의로 2개 선택했을 때 각 노드에서 치킨집 까지 거리와 치킨집을 담을 리스트
    score_list = []
    #조합 구현
    def combinations(arr,r):
        for i in range(len(arr)):
            if r == 1:
                yield [arr[i]]
            else:
                for next in combinations(arr[i+1:],r-1):
                    yield [arr[i]] + next
    #주어진 node를 임의로 2개 선택한다.(조합)
    node_combi = list(combinations([i for i in range(1,n+1)],2))
    #조합을 이용하여 임의로 2개를 선택한 치킨집 노드부터 각 노드까지의 거리를 탐색 / 탐색 종료 후 각 거리의 합을 score_list에 넣어줌
    for nodes in node_combi:
        node1,node2 = nodes #치킨집 2개
        q = [] #BFS로 트리 탐색할 예정 (덱으로 해도됨. 덱 못쓴다는 가정하에 큐 사용)
        q.append([node1,0]) #각 치킨집 노드부터 탐색 시작
        q.append([node2,0])
        scores = [0 for _ in range(n+1)] #치킨집 노드부터 각 노드들의 거리를 저장할 리스트
        visited = [False for _ in range(n+1)] #한번 방문하면 방문하지 않는다. 가장 최소값을 먼저 방문할꺼니까 먼저 방문하면 끝
        visited[node1] = True #치킨집 체크
        visited[node2] = True

        while q: #탐색 시작
            cur_node,depth = q.pop(0) #현재노드, 깊이
            if scores[cur_node] == 0: #아직 방문하지 않은 경우
                scores[cur_node] = depth * 2 #현재 깊이에 2배를 저장한다. 왕복이니까 2배임
            for next_node in tree[cur_node]: #현재 노드에서 연결된 노드를 체크해준다.
                if not visited[next_node]:
                    visited[next_node] = True
                    q.append([next_node,depth+1]) #치킨집노드에서 시작해서 누적해서 온 depth에서 + 1 해줘야함
        score_list.append([sum(scores),node1,node2]) #탐색 종료 후 각 노드 ~ 치킨집노드 거리까지 합과 치킨집 노드를 기록해준다.
    score_list.sort() #거리, node1,node2 순으로 출력하는게 조건이니까 그냥 sort()
    print(f'{score_list[0][1]} {score_list[0][2]} {score_list[0][0]}')

설명

후기

죽어도 플로이드 와샬로 안풀기 위해 BFS를 이용했다.
치킨집 노드부터 탐색을 시작해야 depth 누적해서 거리를 측정할 수 있다.