https://www.acmicpc.net/problem/10473 10473번: 인간 대포 입력은 한 개의 길찾기 문제를 표현한다. 첫 줄에는 두 개의 실수가 입력되며 각각은 당신이 현재 위치한 X, Y좌표이다. 두 번째 줄에는 목적지의 X, Y좌표가 실수로 입력된다. 이어지는 줄에는 대 www.acmicpc.net 다익스트라 알고리즘을 사용하는 문제이다. 우선 이 문제는 그래프를 주지 않았기 때문에 우리가 직접 그래프를 만들어야 한다. 주어진 정점은 시작점, 도착점, n개의 대포이다. 이 정점들의 모든 pair가 그래프의 간선이 된다. 즉 간선의 개수는 (n+2)의 제곱이 되는 것이다. 지금 이 생각까지 코드로 나타내보자. import sys INF=1e9 input=sys.stdin.readline..

https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net https://growth-coder.tistory.com/200 위 포스팅에서 다익스트라 기본 문제를 풀어보았다. 알고리즘 자체는 거의 동일하나 보완할 필요성을 느껴서 기록을 해보려고 한다. 우선 이 문제는 그래프로 표현하기보다는 2차원 배열 그대로 보는 편이 좋다. 연결된 노드들은 동서남북으로 정해져 있기 때문에 동서남북으로 돌면서 체크하는 편이 좋다. 우선 이 문제는 위 포..

https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 다익스트라 알고리즘을 사용하는 문제이다. (다음 링크 참고) https://growth-coder.tistory.com/41 [Algorithm] 다익스트라 (Dijkstra algorithm), 벨만 포드(Bellman ford algorithm) 그래프에서 특정 노드에서 특정 노드까지 가는 최단 거리를 구하는 알고리즘에 대해서 공부해보려 한다. 다익스트라 알고리즘..

그래프에서 특정 노드에서 특정 노드까지 가는 최단 거리를 구하는 알고리즘에 대해서 공부해보려 한다. 다익스트라 알고리즘과 벨만 포드 알고리즘이 있는데 이 둘의 차이는 그래프의 가중치가 음수를 허용하냐 허용하지 않냐의 차이다. 이 둘의 차이점을 기준으로 공부해보려 한다. Dijkstra algorithm 다익스트라 알고리즘은 음의 가중치를 허용하지 않고 양의 가중치만 존재할 때 최단 거리를 구하는 알고리즘이다. 최단 거리를 알고있는 노드와 최단 거리를 모르고있는 노드로 나눈다. 최단 거리를 모르고 있는 노드의 최단거리를 알아내는 것을 반복하는 알고리즘이다. A를 선택하고 연결된 노드 B와 C를 비교한다. 먼저 가장 짧은 거리인 5만큼 떨어져있는 C의 최단 경로는 5라고 확정할 수 있다. 여기서 의문이 생길..