[백준] No.1504 특정한 최단 경로 01

 

1504번: 특정한 최단 경로

이번에 "2024 카카오 채용 연계형 겨울 인턴십" 공고가 떠서 목표로 하고 있다.

지원 분야는 'Data Engineering'으로 11/25(토)에 코딩 테스트를 진행한다고 한다.

저번에 봤던 넥슨은 과제 테스트를 진행했는데, 이번 카카오는 없는 건지 추후 공지인지는 모르겠다.

하지만 확실하게 코딩 테스트를 본다는 것을 알고 있으니 대비해야 한다.

 

친구와 코딩 테스트를 준비하고, 문제를 많이 풀어본 결과

DP, 그리디, 다익스트라, 세 분야에서 보충이 필요하다고 느꼈다.

최근 1달 반동안 알고리즘 및 코딩 테스트 관련 코딩을 하나도 못 하다보니... 다익스트라를 완전히 까먹었다.

DFS, BFS와 기본 Python 문법, 그외 알고리즘들은 종종 봐서 기억나는데, 다익스트라는 진짜 하나도 기억이 안 난다.  

그저 heapq를 사용한다밖에...

그래서 이 문제를 선택했다.

 

문제 자체는 간단하다.

START에서 END로 갈 때, 반드시 point1과 point2(이하 fir와 sec)를 거쳐가야 한다.

이때 최단 거리는 얼마일까요? 없다면 -1을 출력하라는 게 전부인 문제다.

역시 시작은 Pseudo code부터 한다.

 

# ---------- Import ----------
import heapq
import sys
input = sys.stdin.readline

INF = 1e9


# ---------- Function ----------
def Dijkstra(sNode: int, eNode: int):
    return


# ---------- Main ----------
Node, Edge = map(int, input().split())
graph = [[] for _ in range(Node+1)]
distance = [INF] * (Node+1)

# Input graph information
for _ in range(Edge):
    start, end, weight = map(int, input().split())
    graph[start].append((end, weight))
    graph[end].append((start, weight))
    
fir, sec = map(int, input().split())
        
# Print answer
answer = min(way1, way2)
print(answer)

Import 부분에서 다익스트라로 사용할 heapq와 빠른 입력을 위한 sys을 호출했다.

Function 부분에서 시작(sNode)과 끝노드(eNode)를 받는 다익스트라 함수를 작성한다.

Main 부분에서는 문제에서 주어진 입력을 받는다.

그리고 마지막에 가장 짧은 부분을 찾아 정답을 출력한다.

 

# ---------- Main ----------
Node, Edge = map(int, input().split())
graph = [[] for _ in range(Node+1)]

# Input graph information
for _ in range(Edge):
    start, end, weight = map(int, input().split())
    graph[start].append((end, weight))
    graph[end].append((start, weight))

다익스트라 코딩 우선순위는 미뤘다.

왜냐하면 다익스트라는 이미 정해진 틀이 있기 때문이다. 즉,  다익스트라는 단순한 '계산'에 불과하다.

따라서 문제의 주의할 점과 흐름 작성이 먼저라고 생각하여 Main부터 작성하였다.

 

위의 코드는 N(Node)와 E(Edge), graph를 입력받는 부분이다.

이때 distance = [INF] * (Node+1) 부분은 지웠다. 이유는 문제에서 주어진다.

"한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다."

즉 START에서 fir, sec를 거쳐 END로 갈 때, 갔던 간선을 다시 이동할 수 있다는 이야기다.

그럼 연산을 나눠서 START에서 fir로, fir에서 sec로, sec에서 END로 가는 걸 따로 계산해야 한다는 말과 같다.

따라서 위의 distance 부분은 다익스트라를 호출할 때 초기화해줘야 한다. 그래서 함수 내부로 옮겨주었다.

 

그밖에 주의할 점은 문제에서 "방향성이 없는 그래프"라고 주어진다.

start를 기준으로 end에 추가한다면, end를 기준으로 start도 추가해줘야 한다.

 

# ---------- Main ----------
# Two node that must pass
fir, sec = map(int, input().split())
way_distance = [0, 0]

way_condition = [
    [(1, fir), (fir, sec), (sec, Node)],
    [(1, sec), (sec, fir), (fir, Node)]
]

fir와 sec를 거쳐가는 방법은 두 가지가 있다.

1. START > fir > sec > END

2. START > sec > fir > END

 

둘 중 무엇이 더 빠른 방법인지 모르니, 둘 다 계산하고 비교해야 한다.

따라서 way_distance에는 각 방법의 최소 거리를 저장하는 리스트로 선언하고,

way_condition에는 각 방법의 경로를 저장하는 2차원 리스트로 선언한다.

way_distance와 way_condition은 index를 기준으로 mapping한다. 

 

# ---------- Main ----------
# Print answer
way1 = way_distance[0]
way2 = way_distance[1]

if (way1 is None) and (way2 is None): print(-1)
elif way1 is None: print(way2)
elif way2 is None: print(way1)
else: print(min(way1, way2))

문제에서 "그러한 경로가 없을 때에는 -1을 출력한다"라고 적혀있어서 의문이 들었다.

그럼 1번과 2번 경로가 모두 존재하지 않는 경우여야 하는 것 아닌가?

아 그러면 1번만 없을 때, 2번만 없을 때, 1번과 2번 모두 없을 때가 따로 존재하겠구나.

그래서 위의 형태로 코드를 작성했다.

이때 없다는 것을 확실하게 표현하기 위해 None으로 값을 할당했다.

 

# ---------- Main ----------
# Find shortest way
for idx, condition in enumerate(way_condition):
    way = 0
    
    for s, e in condition:
        try:
            way += Dijkstra(s, e)
        except TypeError:
            way = None
            break
    
    way_distance[idx] = way

가장 짧은 거리를 구하는 알고리즘이다.

경로가 존재하지 않는 경우를 None으로 하기로 했다. 하지만 최소 거리는 int 자료형이다.

Dijkstra 함수에서 경로가 없으면 None을 반환할 것이고, 이러면 TypeError가 발생한다.

NoneType과 Int는 서로 더할 수 없다. 따라서 try-except를 활용한다.

 

만약 중간에 한 번이라도 TypeError가 발생한다면, 해당 경로는 미완성이 된다.

따라서 except로 빠질 경우, way에 None을 할당하고, break로 빠져나온다.

그게 아니라면 계속해서 way에 최단 거리(Dijkstra(s, e))를 구하여 더해준다.

최종적으로 다 더한 way는 idx를 기준으로 way_distance에 접근하여 값을 저장한다.

이러면 기본적인 흐름은 전부 작성했다.

이렇게 작성하는데 20분이 조금 넘게 걸렸다.

 

# ---------- Function ----------
def Dijkstra(sNode: int, eNode: int):
    # Start node and distance Init
    distance = [INF] * (Node+1)
    distance[sNode] = 0
    
    # Init
    Q = []
    heapq.heappush(Q, (0, sNode))   # cost, node

기본적인 다익스트라 함수는 sNode(출발 노드)만 받아서, 전체 노드의 최단 거리를 반환한다.

하지만 이 문제에서는 굳이 그럴 필요가 없다고 생각했다.

기점과 종점이 정해져 있으니, 두 노드만 확인하면 되는 거 아닌가?

해서 sNode와 eNode 두 값을 매개변수로 받아들인다.

그 다음 자기 자신의 거리를 0으로 초기화하고, Q에 (cost, node)를 쌍으로 추가한다.

 

# ---------- Function ----------
# Do dijkstra
while Q:
    cost, current_node = heapq.heappop(Q)

    # End condition
    if current_node == eNode:
        return distance[eNode]

    # Check nodes connected with current node
    for next_node, weight in graph[current_node]:
        new_cost = cost + weight

        # New cost is more smallest
        if new_cost < distance[next_node]:
            distance[next_node] = new_cost
            heapq.heappush(Q, (new_cost, next_node))

# No way to go eNode
return None

다익스트라 알고리즘에서 핵심인 부분이다.

Q가 존재한다면 계속해서 pop을 하면서 확인한다.

이때 꺼낸 node(current_node)가 입력받은 종점(eNode)과 일치한다면 조기 종료한다.

내가 원하는 것은 기점과 종점 사이의 최단 거리뿐이지, 다른 것은 불필요하다.

 

아니라면 current_node와 연결된 값들을 하나하나 둘러본다(graph[current_node]). 

이때 새로운 거리(new_cost)가 기존의 거리(distance[next_node])보다 작다면, 업데이트한다.

위 과정을 전부 돌았음에도 불구하고 조기 종료가 되지 않을 수 있다.

이 말은 종점으로 가는 길을 찾지 못했다는 말이다.

return None으로 '갈 수 없음'을 반환하고 함수를 종료한다.

 

다행히도 이번에는 놓친 부분이 없었다.

한 번에 AC를 받을 수 있었다.

 

친구가 코딩 테스트 연습을 할 때 스톱워치를 켜두고 문제를 푼다고 했다.

자기가 얼마나 시간을 소모했고, 얼마나 줄여야 하는지 눈에 보인다고 하길래 이번에 시간을 측정해봤다. 

다행히 한 번에 맞아 45분이 조금 안 걸리는 시간이긴 하다.

이정도면 딱 '무난하다'  그 이상도 이하도 아닌 것 같다.

다익스트라의 구조만 제대로 외운다면 시간을 30분으로 줄일 수 있을 것 같다.

내게 부족한 알고리즘을 외우는 데 시간을 할애해야 겠다.