최단거리
-
[백준]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값이 아닌 값 중 최대 값..
-
[백준]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배열을 사용하여 구현해 주었다. 기본적인 다익스트라 알고리즘을 구현할 수 있는지 묻는 수준의 문제였고 어렵지 않게 풀었..
-
[백준]1238: 파티 - JAVA문제풀이/백준 2021. 2. 17. 17:44
[백준]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에서 모든 마을 까지의 거리를 구하는 방법은 어렵지 않았으나 모든 마을에서 X까지 거리를 구하는 방법이 어려웠다. 결국 각각의 마을에서 X까지 가는 모든 최단거리를 구하고 그 중에 X로 가는 거리만 뽑아내려고 하였다. 그런데 생각해보니 이건 모든 노드에서 모든 노드까지의 최단거리를 구하는 것과 다..
-
[백준]11404: 플로이드 - JAVA문제풀이/백준 2021. 2. 17. 15:11
[백준]11404: 플로이드 www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 풀이 최단거리 알고리즘 공부한 기념으로 관련 문제들을 풀어보았다. 이 문제는 플로이드-워샬 알고리즘을 쓰면 바로 답이 나온다! 모든 정점에서 모든 정점까지의 최단거리를 구하는 문제이다. 문제를 꼭 제대로 읽자! 출력 설명에 i에서 j로 가는 길이 없으면 0을 출력한다고 되어있다. 이를 체크 안해주면 98프로에서 틀린다. 꼭꼭 문제를 제대로 읽자. 코드 1 2 3 4 5 6 7 8 9..
-
[프로그래머스]합승 택시 요금 - JAVA문제풀이/프로그래머스 2021. 2. 17. 13:59
[프로그래머스]합승 택시 요금 programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr 풀이 방향성이 없는 연결 그래프에서 최단 경로를 구해야 하는 문제였..
-
알고리즘 - Shortest PathCS/알고리즘 2021. 2. 16. 22:50
Shortest Path 최단경로 간선 가중치가 있는 유향 그래프에서 두 정점 사이의 최단 경로를 찾는다. Dijkstra Algorithmn 첫 정점을 기준으로 연결되어있는 정점의 거리 정보를 min heap에 넣고 가장 작은 거리를 갖는 정점을 선택한다. (방향성이 있다는 것만 제외하면 MST의 prim알고리즘과 유사하다.) 시작 정점이 A일때, A -> B: 8이고, B -> E: 10이면 A -> E: 18로 갱신해준다. 하나의 정점에서 다른 모든 정점들의 최저 비용을 구한다. 모든 간선의 가중치는 음이 아니어야하고 재방문을 허용하지 않는다. 수행시간: O(ElogV) 구현 with JAVA (백준 1753 최단 경로) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1..