[Algorithm🧬] 정올 1208 : 귀가

문제

A ~ Z a ~ z 를 0 ~ 25 26 ~ 51 에 대응시켜놓고,
무방향 그래프를 그리는데 51 * 51 짜리 배열을 이용하긴 싫어서
딕셔너리로 출발점을 키로해서 [(도착점, 거리)] 배열을 넣었다.

그렇게 넣은 다음에 BFS 로 탐색하는데 소가 있는 (대문자인) 모든 지점에서 출발해야하고,
그 지점부터 Z 까지 가는길을 탐색하며 거리를 줄인다.

import sys
from collections import deque
import math
readl = sys.stdin.readline


def alphabetToIndex(c):
    if ord(c) >= ord('a'):
        return ord(c) - ord('a') + 26

    return ord(c) - ord('A')

def indexToAlphabet(num):
    if num > 25:
        return chr(num - 26 + ord('a'))
    return chr(num + ord('A'))

def BFS(start):
    q = deque([(start, 0)]) # 시간

    while q:
        x, dist = q.popleft()

        # 다음지점과 거리.
        for nx, d in dict[x]:

            ndist = dist + d

            if visited[nx] <= ndist:
                continue

            visited[nx] = ndist
            q.append((nx, ndist))

    return visited[alphabetToIndex('Z')]
            



P = int(readl())
houses = [readl().rstrip().split() for _ in range(P)]

houses = [[alphabetToIndex(start), alphabetToIndex(end), int(dist)] for start, end, dist in houses] + [[alphabetToIndex(end), alphabetToIndex(start), int(dist)] for start, end, dist in houses]

houses.sort()

dict = {x[0] : [] for x in houses}


for start, end, dist in houses:
    dict[start].append((end, dist))

# 소가 없는 목장은 소문자
# 헛간은 Z
    
visited = [math.inf] * 52

# 0 ~ 24 사이에 있는걸 출발점으로 해서 시작.
# 목적지 Z 가 25
min_b = math.inf
min_start = 0
for start, _, _ in houses:
    if start < alphabetToIndex('Z'):
        b = BFS(start)
        if min_b > b:
            min_b = b
            min_start = start
        # print(start, b)
            
print(indexToAlphabet(min_start), min_b)