[24042번] 횡단보도(다익스트라)

2023. 4. 5. 21:56·Coding Test/Graph
728x90
 

24042번: 횡단보도

당신은 집으로 가는 도중 복잡한 교차로를 만났다! 이 교차로에는 사람이 지나갈 수 있는 $N$ 개의 지역이 있고 그 지역 사이를 잇는 몇 개의 횡단보도가 있다. 모든 지역은 횡단보도를 통해 직,

www.acmicpc.net

 

분석

  • 시간 역행 불가, 이미 지난 가중치로 지나갈 수 없음 ➔ 주기
  • 이전 소요 시간 ≤ 지금 이용하는 시간 값이 될 때까지 M을 여러 번 더하여(곱하여) 사용

 

풀이

import heapq
import sys
input = sys.stdin.readline

n, m = map(int, input().split())

graph = [[] for _ in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    graph[a].append((i, b))
    graph[b].append((i, a))


def dijkstra():
    d = [sys.maxsize for _ in range(n + 1)]
    d[1] = 0

    q = []
    heapq.heappush(q, (0, 1)) # 시작 노드 1

    while q:
        cost, node = heapq.heappop(q)

        # 현재 노드가 이미 처리된 적이 있는 노드라면 무시
        if d[node] < cost:
            continue

        # 현재 노드와 연결된 다른 인접한 노드들을 확인
        for ncost, nnode in graph[node]:

            # 주기
            tmp = (cost-ncost)//m
            if (cost - ncost) % m != 0:
                tmp+=1
            ntime = ncost+tmp*m

            # 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
            if d[nnode] > ntime+1:
                d[nnode] = ntime+1
                heapq.heappush(q, (ntime+1, nnode))
    return d[n]

print(dijkstra())

 

 

728x90
저작자표시
'Coding Test/Graph' 카테고리의 다른 글
  • [1325] 효율적인 해킹(BFS)
  • [18352] 특정 거리의 도시 찾기(다익스트라・heapq, BFS・deque)
  • 그래프의 표현 및 비교 (간선 리스트, 인접 행렬, 인접 리스트)
  • [1197번] 최소 신장 트리(MST, 크루스칼, 프림, 유니온파인드)
Karla Ko
Karla Ko
𝘾𝙤𝙣𝙩𝙞𝙣𝙪𝙤𝙪𝙨𝙡𝙮 𝙄𝙢𝙥𝙧𝙤𝙫𝙞𝙣𝙜, 𝘾𝙤𝙣𝙨𝙩𝙖𝙣𝙩𝙡𝙮 𝘿𝙚𝙫𝙚𝙡𝙤𝙥𝙞𝙣𝙜 𝙔𝙚𝙨!
    250x250
  • Karla Ko
    karlaLog
    Karla Ko
  • 전체
    오늘
    어제
    • Total (467)
      • Spring (19)
      • JPA (4)
      • Cloud & Architecture (15)
        • Kubernetes (5)
        • Docker (3)
        • MSA (2)
        • GCP (1)
        • AWS (4)
      • Devops (1)
      • Message Queue (4)
        • Kafka (2)
        • RabbitMQ (2)
      • Git (4)
      • DB (4)
      • Java (9)
      • Python (4)
      • CS (11)
        • OS (8)
        • Network (2)
        • Algorithm (1)
      • Coding Test (392)
        • programmers (156)
        • Graph (43)
        • DP (37)
        • Search (31)
        • Tree (13)
        • Data Structure (26)
        • Combination (12)
        • Implement (18)
        • Geedy (23)
        • Sort (7)
        • Math (21)
        • geometry (2)
  • 블로그 메뉴

    • 홈
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    조합
    최단거리
    프로그래머스
    스택
    이분탐색
    동적계획법
    최소신장트리
    알고리즘
    덱
    트리
    다익스트라
    그래프
    정렬
    재귀
    힙
    BFS
    DFS
    구현
    그리디
    플로이드워셜
    LIS
    파이썬
    DP
    자료구조
    구간합
    백준
    큐
    월간코드챌린지
    최대공약수
    Algorithm
  • hELLO· Designed By정상우.v4.10.3
Karla Ko
[24042번] 횡단보도(다익스트라)
상단으로

티스토리툴바