다익스트라
-
[백준]22255: 🦖호석사우루스 - JAVA문제풀이/백준 2021. 7. 31. 15:51
[백준]22255: 호석사우루스 22255번: 호석사우루스 (1, 1) -> (2, 1) -> (2, 2) -> (2, 3) -> (3, 3) -> (3, 4) -> (4, 4) -> (5, 4) -> (5, 5) 8번 만에 갈 수 있고 이게 최소이다. www.acmicpc.net 풀이 🪑 시작 노드에서 도착 노드로 가는 최소 비용을 구하는 문제이다. (최단 거리 아님!) 한 정점에서 다른 정점으로 가는 최소비용! 다익스트라 문제이다. 📝 문제의 조건을 정리해 보자!' 3K번째 이동: 상 하 좌 우로 이동 가능하다. 3K + 1번째 이동: 상 하로 이동 가능하다. 3K + 2번째 이동: 좌 우로 이동 가능하다. 시작노드 ~ 도착노드로 가는 최소 비용을 구한다. 🔧 문제 풀이 과정은 다음과 같다. 다익스트..
-
[백준]17396: 백도어 - JAVA문제풀이/백준 2021. 7. 25. 22:46
[백준]17396: 백도어 17396번: 백도어 첫 번째 줄에 분기점의 수와 분기점들을 잇는 길의 수를 의미하는 두 자연수 N과 M이 공백으로 구분되어 주어진다.(1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000) 두 번째 줄에 각 분기점이 적의 시야에 보이는 www.acmicpc.net 풀이 🪑 문제가 좀 복잡해 보여서 그렇지 사실 문제에 필요 없는 정보를 제외하면 그냥 최단거리 문제이당. 📝 문제를 푸는데 필요한 조건만 정리해 보자. 0에서 N-1번째 분기점 까지 가는 최단 거리를 구해준다. 이때 시야 정보도 주어지는데 0이면 해당 분기점일 때 상대 시야에서 보이지 않는다는 의미이고, 1이면 상대 시야에서 보인다는 의미이다. 시야에서 보이지 않으면서 N-1번째 분기점으로 갈 수 있는 최단거리..
-
[백준]20926: 얼음 미로 - JAVA문제풀이/백준 2021. 7. 23. 17:23
[백준]20926: 얼음 미로 풀이 🪑 구현 + 다익스트라 문제이다. 📝문제의 조건을 정리해보자. 얼음 미로에서는 한 방향으로 이동시 바위나 출구를 만날때 까지 멈출 수 없다. 바깥은 절벽이다. T: 상하좌우로 이동할 수 있다. R: 통과할 수 없으며 부딪히면 멈춘다 H: 이곳에 빠지면 탈출할 수 없다. E: 미로를 탈출하는 유일한 출구이다. 각 위치마다 미끌시간이 존재하며 탈출할 수 있는 최단 미끌시간을 구한다. 🔧 다음과 같은 풀이를 생각해 주었다. 다익스트라를 사용한다. 한번 이동할 때 해당 방향으로 이동할 수 있는지 먼저 확인한다. 이동 가능하면 그 방향으로 갈 수 있는 곳까지 간다. 도착한 후 더 짧은 미끌시간을 계산해 준다. 도착 노드의 최단 미끌시간을 출력한다. 📌 처음엔 70 ~ 80프로 ..
-
[백준]5972: 택배 배송 - JAVA문제풀이/백준 2021. 5. 24. 10:53
[백준]5972: 택배 배송 https://www.acmicpc.net/problem/5972 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net 풀이 출발지 헛간에서 목적지 헛간으로 가는 최소 거리를 찾는 문제로 다익스트라 알고리즘을 활용하여 풀었다. 다익스트라를 사용하여 출발지에서 다른 모든 헛간으로 가는 최소 거기를 찾아준 다음, 목적지까지의 거리를 반환해 주었다. 헛간 사이에는 방향성이 없으므로 헛간간의 거리를 입력받을때, 입력받는 두 개의 헛간에 모두 정보를 입력해 주었다. 또한 dist의 default값은 입력..
-
[백준]11779: 최소비용 구하기2 - JAVA문제풀이/백준 2021. 5. 17. 14:45
[백준]11779: 최소비용 구하기2 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 풀이 최소 비용을 구하면서, 최소 비용 경로까지 함께 구하는 문제였다. 출발 노드가 정해져 있으므로 다익스트라 알고리즘을 사용하여 출발 노드로 부터 모든 노드까지의 최소 비용을 구해주었다. 처음에는 다익스트라 알고리즘 내부에서 우선순위 큐(최소 힙)에 노드를 넣어 주는 것을 최소 비용 경로로 계산해 주었다. 하지만 이는 정답이 ..
-
[백준]10282: 해킹 - JAVA문제풀이/백준 2021. 4. 29. 17:41
[백준]10282: 해킹 www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 풀이 서로 의존성을 가지고 연결된 컴퓨터들 끼리 전염이 되는데 최대 전염 컴퓨터의 수와 전염될 수 있는 컴퓨터가 모두 전염되었을 때의 시간을 반환하는 문제이다. 첫 시작 컴퓨터를 기준으로 다른 모든 컴퓨터가 전염되는 시간을 구하는 문제임으로 다익스트라 알고리즘을 사용하여 문제를 풀었당. 다익스트라 알고리즘을 실행한 후 dist함수에서 Integer.MAX_VALUE값이 아닌 값 중 최대 값..
-
[백준]2665: 미로만들기 - JAVA문제풀이/백준 2021. 4. 11. 15:44
[백준]2665: 미로만들기 www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1≤n≤50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 풀이 BFS + 다익스트라를 활용하여 풀었다. 첫 노드에서 오른쪽 아래 노드로 가는 최단 거리 중에서 검은색 벽을 가장 적게 바꾸는 방법의 횟수를 출력하는 문제로 이전에 풀었던 '벽 부수고 이동하기'와 유사한 문제였다. 검은색 벽을 흰색 벽으로 바꾸는 최소 횟수를 누적하여 계산하며 탐색하기 위해 다익스트라 방법을 사용하였다. dist배열을 사용하여 현재 위치의 가장 최소 횟수를 저장할 수 ..
-
[백준]1240: 노드사이의 거리 - JAVA문제풀이/백준 2021. 3. 28. 16:28
[백준]1240: 노드사이의 거리 www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. www.acmicpc.net 풀이 두 노드 사이의 최단 경로를 반환하는 문제였다. 다양한 방법이 있겠지만 나는 다익스트라 알고리즘을 사용하여 풀었다. 노드와 간선 가중치의 정보를 입력 받은 후 M개의 개수 만큼 다익스트라 알고리즘을 돌려 M개의 거리를 출력하였다. 다익스트라 알고리즘은 우선순위 큐(최소힙)와 dist배열, visited배열을 사용하여 구현해 주었다. 기본적인 다익스트라 알고리즘을 구현할 수 있는지 묻는 수준의 문제였고 어렵지 않게 풀었..