백준 1595 북쪽나라의 도로 파이썬 풀이

난이도 : 골드4

풀이일 : 2403284

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

1595번: 북쪽나라의 도로

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

풀이코드

import sys
from collections import deque


def BFS(n):
    queue = deque([n])
    visited = [-1] * 10001  # 방문 확인 및 거리 저장
    visited[n] = 0  # 현재 노드까지의 거리 설정
    while queue:
        x = queue.popleft()
        # x와 연결된 도시 방문
        for nx, add in world[x]:
            # 방문한 적이 없는 도시라면, 거리 저장
            if visited[nx] < 0:
                visited[nx] = visited[x] + add
                queue.append(nx)
    return visited


world = [[] for _ in range(10001)]  # 최대 수 10000 고려
while True:  # 입력이 있는 만큼 처리
    try:
        s, e, d = map(int, sys.stdin.readline().split())
        world[s].append([e, d])
        world[e].append([s, d])
    except:
        break

temp = BFS(1)  # 아무 지점에서나 가장 거리가 먼 노드 탐색
idx = temp.index(max(temp))  # 가장 거리가 먼 노드 인덱스 저장

temp = BFS(idx)  # 인덱스 노드에서 가장 거리가 먼 노드 탐색
print(max(temp))  # 최장거리 출력

• 입력의 크기에 대한 정보가 없기 때문에, try, except문으로 더 이상 입력값이 주어지지 않을 때까지 입력을 받아 처리하였다.
• world : 최대 도시의 수가 10000개로 제한되어 있고, 따로 도시의 수가 주어지지 않으므로 10001칸으로 설정하였다.
• 아무 도시에서나 가장 거리가 먼 도시를 구하고, 구한 도시에서부터 가장 거리가 먼 도시까지의 거리를 구해 출력한다.
• idx : 아무 도시에서나 가장 거리가 먼 도시를 구한 뒤, 해당 도시를 기록하기 위한 변수로 사용하였다.
• temp : visited 배열을 그대로 받아, visited 배열에서 최고값과 인덱스를 구하기 위한 변수로 사용하였다.
• visited : 거리가 0인 배열이 있는지, 초기 값을 0으로 설정해두었을때는 통과하지 못했다. 0이 도시간의 거리로 주어질 경우를 대비하기 위해여 -1로 초기값을 설정한다.
• 방문하지 않은 도시에 대해, 도시를 방문처리하며 visited에 현재까지의 거리 + 새로운 이동 거리 정보를 추가하여 저장한다.

---

느낀점

• 처음에는 최단거리 문제로 인식해서 heapq를 사용하고, 거리를 -d로 추가하는 방식으로 풀었다가 틀렸다. 초기 설정 때문인 것 같으니까 그 방법으로도 다시 풀어봐야지.
• 한 유형의 문제를 계속 모아풀면, 다른 풀이 방법을 충분히 떠올리기 전에 냅다 익숙한 방식으로 로직을 세우는 것 같아서 반성했다.

---

추가

import sys, heapq

def sol(n):
    queue = []
    visited = [1] * 10001  # 방문 확인 및 거리 저장
    visited[n] = 0  # 현재 노드까지의 거리 설정
    heapq.heappush(queue, [0, n])
    while queue:
        cost, x = heapq.heappop(queue)
        if cost > visited[x]:
            continue
        for add, nx in world[x]:
            if visited[nx] > 0:  # 방문하지 않은 도시 방문 처리
                visited[nx] = cost + add
                heapq.heappush(queue, [cost + add, nx])
            if cost + add > visited[nx]:  # 더 빠른 거리 발견 시 거리 재설정
                visited[nx] = cost + add
                heapq.heappush(queue, [cost + add, nx])
    return visited

world = [[] for _ in range(10001)]  # 최대 수 10000 고려
while True:  # 입력이 있는 만큼 처리
    try:
        s, e, d = list(map(int, sys.stdin.readline().split()))
        world[s].append([-d, e])  # 최대힙으로 사용하기 위해 음수로 저장
        world[e].append([-d, s])
    except:
        break

temp = sol(1)  # 아무 도시에서나 가장 거리가 먼 도시 탐색
idx = temp.index(min(temp[1:]))  # 가장 거리가 먼 도시 정보

temp = sol(idx)  # 찾은 도시에서 가장 거리가 먼 도시
print(-min(temp[1:]))  # 가장 먼 두 도시의 거리 출력

• 맨 처음 heapq를 사용하여 최단거리 경로를 찾는 방식으로 풀이하였던 것도 최초 visited 설정을 수정하여 통과하였다.
• 위에 올린 코드보다 메모리는 조금 더 쓰고 시간은 조금 더 빠른데 크게 의미가 있는 정도는 아닌 것 같다.
• 문제 조건에서, 북쪽 나라는 임의의 두 도시를 지나는 경로가 유일하다고 적혀있기 때문에 기존 코드가 더 적합한 풀이라고 생각한다. 추가코드는 우선순위 큐와 다익스트라를 사용하는데 북쪽나라가 트리 구조라서 메리트가 크게 떨어지니까. BFS 풀이가 쉽고 직관적이고 쓰잘데기 없는 짓도 덜 하는 느낌이다. 그래도 풀긴 풀었으니까 이것도 남겨보기로.