코딩스토리

www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 다익스트라 알고리즘을 사용한 문제이다. 최단거리를 찾아야 하나 가중치가 존재한다. 즉 전형적인 다익스트라 알고리즘 문제이다. 문제는 지금까지 인접 리스트를 활용해서 풀어보다 보니 이렇게 그래프로 모델링해서 풀어본 적이 없었다. 구현 자체는 문제가 없었는데 고민했던 부분은 우선순위 큐에서 우선순위를 어떻게 주어야 하는지였다. 내가 사용하고 싶은 것은 dis, x좌표, y좌표 이 3가지였기 때문에..

www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 다익스트라 알고리즘을 활용한 문제이다. 문제에서 확인해야 하는 조건들 1. 방향성이 없는 그래프 -> 무방향 그래프, 즉 양방향 그래프가 된다. (입력받을 때 처리) 2. 임의로 주어진 두 정점은 반드시 통과해야 한다. -> 두 정점을 거쳐서 가야함 3. 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동 가능 -> 각각의 중간 정점에 가서 새롭게 다익스트라..

www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 다익스트라 알고리즘 관련 문제이다. 처음 봤을 때 어떻게 해야 할지 감은 잡혔으나 그걸 코드로 옮기는 게 너무 어려웠다.. 먼저 떠올렸던 해법은 1. 다익스트라를 통해 시작점부터 도착점까지 최단 거리를 구한다. 2. 최단 경로에 포함된 간선들을 모두 제거한다. 3. 다익스트라를 통해 거의 최단 경로를 구한다. 문제는 2번이였다. 최단 경로가 여러 개가 나올 수 있고, 그렇다면 그 ..

www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 다익스트라를 활용한 문제이다. 문제 분석 기본적인 다익스트라 문제이다. 버스 비용이 다르다 -> 가중치가 다르다, 즉 다익스트라! 도시를 노드로, 버스 비용을 간선으로 바꾸어 그래프 문제로 모델링하면 된다. 이 문제의 특이한 점은 출력 조건이였다. 1. 출발 도시에서 도착 도시까지 가는데 드는 최소 비용 출력 2. 경로에 포함되어있는 도시의 개수 3. 도시 순서대로 출력 최소 비..

www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 다익스트라 알고리즘을 작년 8월에 처음 공부한 뒤 지금까지 한 번도 복습하지 않았다.. 당연히 그때도 어려웠지만 지금은 완전히 까먹은 상태여서 언젠간 해야지 하다가 결국 어제오늘 복습을 했다. 사실 bfs 문제를 풀다가 '가중치'가 일정하지 않은 문제를 만나서 급하게 다익스트라를 공부한거긴 함ㅎㅎ 어쨌든 문제를 분석해보면 도로들은 단방향으로 이루어져있고 -> 단방향 그래프 각각의 ..