-
[BOJ - 5719] 거의 최단 경로(Python,파이썬)백준알고리즘 2020. 4. 23. 01:28
https://www.acmicpc.net/problem/5719
5719번: 거의 최단 경로
문제 요즘 많은 자동차에서는 GPS 네비게이션 장비가 설치되어 있다. 네비게이션은 사용자가 입력한 출발점과 도착점 사이의 최단 경로를 검색해 준다. 하지만, 교통 상황을 고려하지 않고 최단 경로를 검색하는 경우에는 극심한 교통 정체를 경험할 수 있다. 상근이는 오직 자기 자신만 사용 가능한 네비게이션을 만들고 있다. 이 네비게이션은 절대로 최단 경로를 찾아주지 않는다. 항상 거의 최단 경로를 찾아준다. 거의 최단 경로란 최단 경로에 포함되지 않는 도로로만
www.acmicpc.net
전에 C++로 풀어보았던 문제다.
C++로 했을때는 중복을 허락하는 BFS를 두번 써서 해결을 했던것으로 기억한다.
그런데, Python에서 그와 같은 방법을 쓰기에는 파이썬은 굉장히 느렸고 불편했어서
다익스트라를 두번 쓰는 방법을 선택했다.
'백준알고리즘' 카테고리의 다른 글
[BOJ - 1647] 도시 분할 계획 ( 순수 C언어 ) (0) 2020.04.27 [BOJ - 11812] K진 트리 (0) 2020.04.26 [BOJ - 16234] 인구 이동(Python,파이썬) (0) 2020.04.23 [BOJ - 9466] 텀 프로젝트(Python, 파이썬) (0) 2020.04.23 [BOJ - 1939] 중량제한 (파이썬,Python) (0) 2020.04.18