• Home
  • About
    • Hooni photo

      Hooni

      Hooni coding

    • Learn More
    • Email
    • Instagram
    • Github
  • Posts
    • All Posts
    • All Tags
  • Projects

2021 하계 모각코 4주차 목표와 회고

25 Jul 2021

Reading time ~1 minute

4주차 (07월 25일)

목표

  • 알고리즘 < 최단경로 > 문제풀기 (백준 1753번, 백준 1504번)

회고

  • 알고리즘 < 최단경로 > 문제 : 백준 1753번(“최단경로”) -> 난이도 : 골드5

image

해결 방법 : 가중치가 있고 방향이 있는 그래프에서 한 정점에서 다른 모든 정점까지 최단거리를 구할때는 다익스트라 알고리즘을 사용한다.(모든 정점 간의 최단거리를 구할 때는 플로이드워셜 알고리즘 사용)

코드일부

while queue:
    w, cur = heapq.heappop(queue)
    if w > distance[cur]:
        continue
    for weight, end in graph[cur]:
        if w + weight < distance[end]:
            distance[end] = w + weight
            heapq.heappush(queue, (weight + w, end))
  • 알고리즘 < 최단경로 > 문제 : 백준 1504번(“특정한 최단경로”) -> 난이도 : 골드4

image

해결 방법 : 시작점에서 다익스트라 사용, 거쳐가는 점 v1, v2에서 각각 다익스트라 사용해서 총 다익스트라를 3번 사용하여서 거쳐가는 최단거리를 구한다.

코드일부

def dijkstra(start, goal):
    distance = [INF] * (N + 1)
    queue = []
    heapq.heappush(queue, (0, start))
    distance[start] = 0
    while queue:
        w, cur = heapq.heappop(queue)
        if w > distance[cur]:
            continue
        for weight, end in graph[cur]:
            if w + weight < distance[end]:
                distance[end] = w + weight
                heapq.heappush(queue, (weight + w, end))
    return distance[goal]

case1 = dijkstra(1, v1) + dijkstra(v1, v2) + dijkstra(v2, N)
case2 = dijkstra(1, v2) + dijkstra(v2, v1) + dijkstra(v1, N)
if min(case1, case2) < INF:
    print(min(case1, case2))
else:
    print(-1)


2021 하계 모각코 Share Tweet +1