본문 바로가기

다익스트라6

BOJ 1446 지름길 www.acmicpc.net/problem/1446 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하이고, D는 10,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주 www.acmicpc.net 문제는 그리디 하게 접근해야 한다는 것이다. 그냥 지름길이 주어졌다고 해서 지금 길만 탄다면 다른 컴포넌트에 있는 길로 가는 것이 더 빠를 수 있다. 어떻게 접근해야 할까? 핵심은 다익스트라를 돌리면서 현재 위치 + 1 에 지름길이 없다면 우선순위 큐에 cost + 1 로 넣어주는 것이다. 이렇게 되면 자연히 d 이하의 모든 노드를 탐색하면서 지름길이 있다면 지름길을 타고, 아니라면 다음 컴포넌트가 .. 2020. 12. 16.
BOJ 4485 녹색 옷 입은 애가 젤다지? www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net BFS + 다익스트라 조합으로 풀면 된다. 기존 다익스트라는 1차원 배열에서 각 정점의 최단거리를 구했지만 이 문제에서는 2차원 배열로 선언해서 각 구간에 가기 위해서 우선순위 큐를 사용해서 최단거리로 갱신하며 이동한다. #include #include #include using namespace std; const int inf = 1e9; int ar[126][126], n; bool vi.. 2020. 11. 6.
BOJ 1238 파티 www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 다익스트라 응용문제로, 단방향 그래프의 방향을 바꿔서 다익스트라를 돌리면 모든 정점에서 한 정점으로 가는 거리를 구할 수 있다. 따라서 파티장 x가 주어지면 a에서 b로 가는 그래프 외에 b에서 a로 가는 그래프도 입력을 받아주고 각각에 대해서 다익스트라를 사용한 뒤에 두 배열의 합 중에서 가장 큰 값이 정답이 된다. #include #include #include using na.. 2020. 11. 5.
BOJ 9370 미확인 도착지 www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 첫 번째 줄에 3개의 정수 n, m, t (2 ≤ n ≤ 2 000, 1 ≤ m ≤ 50 000 and 1 ≤ t ≤ 100)가 주어진다. 각각 교차로, 도로, 목적지 후보의 개수이다. 두 번째 줄에 3개의 정수 s, g, h (1 ≤ s, g, h ≤ n)가 주어진다. s는 예술가들의 출발지이고, g, h는 문제 설명에 나와 있다. (g ≠ h) 그다음 m개의 각 줄마다 3개의 정수 a, b, d (1 .. 2020. 11. 5.
BOJ 1261 알고스팟 www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 다익스트라와 BFS를 활용한 최단거리 찾기 문제였다. 이 문제는 다익스트라를 처음 배우고 풀어보려 했었는데 도저히 어떻게 풀어야 할지 몰라서 포기했는데 다익스트라를 좀 더 이해하고 보니 어떻게 활용해야 풀 수 있을지 알았다. 기존 다익스트라는 일차원 배열을 통해 한 노드에서 다른 모든 노드를 가는 최단거리를 구하지만 이번 문제에선 2차원 배열을 통해 각 배열의 최단거리를 구해준다. 입력은 .. 2020. 11. 4.
다익스트라 알고리즘 이번에는 다익스트라 알고리즘을 공부해 봤다. 사실 다익스트라는 너무 잘 알려진 알고리즘이라 다른 여러 블로그들을 참고해서 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 이 문제를 푸는 식으로 알아봤다. const int INF = 1e9; vector ar[20001]; // ar[from].push_back({to, cost}) from -> to , 가중치 vector d; // 거리값을 갱신해주는 배열 일단 기본적으로 가중치.. 2020. 9. 24.

티스토리툴바