hw.dev

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 📌 해결순서 이번에 풀 때도 마찬가지로 times 배열을 만들어서 방문 표시와 걸리는 시간의 표시를 같이 묶어서 하려고 했는데 이 문제에서는 그렇게 하면 안된다. 5에서 첫 번째 이동을 예시로 들면 (4, 6, 10) 으로 이동할 수 있는데 4, 6 은 시간이 +1 되기 때문에 상관이 없지만 10은 방문 했음에도 불구하고 +0을 하기 때문에 여전히 방문하지 않은것..

https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 📌 해결순서 다익스트라 기본 문제와 매우 비슷한 문제, 조금 조건만 추가 됐다. 최단경로를 구하는 것은 동일 하지만, 지정한 두 정점을 무조건 거쳐야 하므로 두 정점에서 출발하여 다른 모든 노드로 가는 최단경로 테이블을 각각 만들어 주면 쉽게 해결할 수 있겠다고 생각했다. 테이블을 총 3개 만들어야 하니까, 함수 호출을 3번 해주면 되겠군.. 이렇게 생..

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 📌 해결순서 다익스트라 알고리즘의 제일 기본적인 유형 문제를 풀기전에 다익스트라 알고리즘의 동작과정부터 생각해보자. 위의 그림과 같은 방향 그래프가 있다고 생각해보자 목표는 1번노드에서 출발해 2, 3, 4 노드로 이동하는데 드는 최소 비용을 저장하는 Distance Table 을 구하는 것이다. 탐색을 시작하기 전에 모든 노드는 방문하지 않았으므로, 거리를 ..