개발하는 개구리

🐸 문제 정보 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net 🤖 알고리즘 다익스트라 ⏱️ 풀이 시간 07.49m 📝 풀이 다익스트라 + 최단경로 구하기의 정석같은 문제였다. 별 다른 구현 없이, 다익스트라 알고리즘만 구현할 수 있으면 풀 수 있었다. 해당 알고리즘은 이전에 정리해둔 포스팅이 있으니 아래에서 참고하면 좋을 것 같다. 최단 경로 찾기 with Python 🌊 최단 경로 찾기 알고리즘 🐸 이해하기 최단경로 찾기 알고리즘? 노드 간 가중치가 주어질 때, 시작 노드부터 모든 노드까지의 최소값을 구하는 알고리즘..

🐸 문제 정보 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이 www.acmicpc.net 🤖 알고리즘 다익스트라 ⏱️ 풀이 시간 30.05m 📝 풀이 최근에 공부한 최단거리 포스팅을 읽어보면 쉽게 풀 수 있는 문제였다. 모든 거리 지점을 노드라고 생각하고, 각 지점에서 다음 지점까지 가중치 1씩을 기본으로 설정했다. 그리고 지름길이 있는 부분에 간선을 추가하여 다익스트라를 돌리면 되는 문제였다. 최단 경로 찾기 with Python 🌊 최단 경로 찾기 알고리즘 🐸 이해하기 최단경로 찾기 알고리즘? 노드 간 가중치가 주어질 때..

🌊 최단 경로 찾기 알고리즘 🐸 이해하기 최단경로 찾기 알고리즘? 노드 간 가중치가 주어질 때, 시작 노드부터 모든 노드까지의 최소값을 구하는 알고리즘이다. 이해하는데에 큰 어려움은 없었고, 이전 블로그에서 한 번 코드를 아카이빙 한 적 있지만 자꾸 까먹어 아예 각 잡고 정리를 해야겠다 싶었다. 정리하면서 참고한 글은 포스트 최하단에 링크되어있다. 최단 경로를 찾는 문제는 크게 세가지로 나뉜다. 특정 노드에서 특정 노드까지의 최단 경로 ⭢ 다익스트라 알고리즘 특정 노드에서 모든 노드까지의 최단 경로 가중치가 모두 양수인 경우 ⭢ 다익스트라 알고리즘 가중치에 음수가 있는 경우 ⭢ 벨만 포드 알고리즘 모든 노드에서 모든 노드까지의 최단 경로 ⭢ 플로이드 워셜 알고리즘 즉 저 세개의 알고리즘은 어쨌든 그래프에..