다익스트라
-
BOJ) 특정한 최단 경로 (1504 번)알고리즘/백준 2021. 1. 29. 17:14
특정한 최단 경로 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 다익스트라를 사용한다는 조건에 노드 두 개를 거쳐야하는 경로에 포함해야하는 문제다. 처음에는, 기본적인 다익스트라로 경로를 이동하면서 입력받은 두 노드를 거쳤는지 정보도 함께 포함했었다. 하지만, 틀린 것을 확인하고 두 경로 모두 거쳐야하는 조건을 제대로 파악하기 어렵다고 생각했다.그래서 경로가 두개만 주어지기 때문에, 해당 경로를 거치는 경우의 수를 다익스트라로 표현하면 된다고 생각했다. 풀이 1번..
-
BOJ) 알고스팟 (1261 번)알고리즘/백준 2021. 1. 21. 18:22
알고스팟 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 문제 벽이 존재하는 미로에서 처음 위치 (0,0)를 시작으로 (n-1,m-1)까지 도착해야한다. 이 때, 최소한으로 벽을 부시면서 경로를 찾는 문제다. 최소 + 경로 => 다익스트라를 이용하면 되겠다고 판단했다. 풀이 풀이는 간단하다. 일반적인 다익스트라를 구현하는 것 처럼 우선순위 큐를 활용해서 풀었다. 우선순위는 벽을 가장 적게 허문 순서대로 정렬했고, 이동하는 곳이 벽인 경우에는 +1을, 벽이 아닌 경우에는 +0을 해주며 길을..
-
BOJ) 녹색 옷 입은 애가 젤다지? (4485 번)알고리즘/백준 2021. 1. 19. 00:33
녹색 옷 입은 애가 젤다지? 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 다익스트라를 알고, 적절하게 이용할 줄 아는가?를 물어보는 문제였다. 좌측 상단에서 우측 하단으로 이동하면서 돈을 가장 적게 뺏겨야하는 문제다. 처음에는 dp로 간단하게 풀 수 있겠다고 생각하고 코드를 작성했지만, 불규칙적으로 왔다갔다하는 경우가 있어서 다익스트라를 추가해줬다. 출발 지점을 우선순위 큐에 담아두고, 상하좌우를 돌면서 돈을 가장 적게 뺏기는 경우들을 저장하면서 큐에 넣어주었다. 이동하면서, 가장 적게 ..
-
프로그래머스 Lv.3) 배달알고리즘/프로그래머스 2020. 5. 31. 23:03
배달 코딩테스트 연습 - 배달 5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4 programmers.co.kr 풀이 문제를 보고 많은 생각이 스쳐 지나갔다. MST가 먼저 떠올랐는데, 모든 경로를 잇는 것이 중요한 문제가 아니기 때문에 아니라고 생각했다. 다음은, 최단 거리 알고리즘이었다. 다익스트라(dijkstra) 이름이 기억나지 않았지만, 이 로직이 떠올랐다. 하지만, 처음에 풀었을 때는 edge를 따로 저장하지 않고, 주어진 road만 돌면서 우선순위 큐에 저장하고 최소 비용으로 잘 잇는다면 가능하지 않을까 싶었다. 결과는 40점, ..