Hansel

최단거리를 구하는 문제이다. 내일로 티켓을 사용해서 최단 비용으로 경로를 지나갈때 드는 총 비용과 내일로 티켓을 사용하지 않고 최단 비용으로 경로를 지나갈때 드는 총 비용을 비교하면 된다. 모든 경로상의 비용이 필요하기 때문에 플로이드 와샬이 적합한 문제이다. 우선 K개의 교통수단이 주어지면서 비용을 입력해두는데 티켓이 필요하지 않은 경로의 경우 가장 싼 가격을 입력해두고 티켓이 필요한 경로는 교통수단의 종류에 맞게 분류를 하고 가격을 입력하면 된다. 그 후 플로이드와샬 알고리즘을 돌려서 두 경로의 결과를 비교하면 된다. package TT5_MAY; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamR..

문제 자체는 사람을 건너 건너 연결하다 보면 결국 이어진다는 얘기다. 출력으로는 그런 케빈 베이컨 게임을 했을 때 가장 적은 경로로 이어지는 사람을 찾아야 한다. 사람을 연결하는 것이니 처음엔 Union Find 인가? 싶기도 했지만 그림을 한번 그려보면 바로 어떤 자료구조를 사용하는 알고리즘인지 답이 나온다. 그림을 그려보면 결국 그래프를 이용한 최단거리를 찾는 문제가 된다. 1. N개의 시작점에서 모든 경로 사이의 최단 거리를 구하고 더한다. 2. 더해진 최단 거리들 중에서 가장 적은 수를 가진 인덱스를 출력한다. 끝 package TT4_APR; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamR..

사이클이 어떻게 형성되는지 확인하면 쉽게 풀 수 있는 문제이다. 문제에서 나오는 점들은 일직선 위에 놓여있지 않다. 따라서 일직선 위에 점을 놓고 주어진 입력대로 해보면 사이클이 생기는걸 볼 수가 없다. 일반적인 그래프를 그리고 입력에 따라 선분을 그어보면 사이클이 형성되는 시점을 포착할 수 있다. 두 점이 같은 집합에 속한다면(부모가 같다면) 그 점은 사이클을 이루게 된다. 따라서 주어진 입력에서 두 점이 부모가 같다면 그때 사이클이 형성되므로 답을 출력한뒤에 종료시키고 아니라면 계속 반복문을 돌면 된다. package Mar_2022; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; ..

이 문제는 다익스트라 알고리즘을 이용한 약간의 응용이 필요하다. 응용이라 해도 결국 최단거리의 루트를 출력하는 것이라 큰 응용은 아니다. 우선 다익스트라와 우선순위 큐를 이용해 최단거리를 구하는 것은 다른 최단거리 알고리즘과 동일하다. 하지만 어떤 경로를 통해 최단 거리를 구해냈는지를 출력하는게 이 문제의 목적이다. 나는 우선순위큐에 다음 목적지, 이동 거리, 이전 노드를 함께 넣었다. 그리고 우선순위큐에서 다음 목적지를 빼낼때(Poll) 그 목적지가 아직 방문표시가 안되어 있다면 결과를 저장하는 arraylist에 추가하고 방문 처리를 해줬다. 우선순위 큐의 특성으로 poll을 할 때 마다 결국 최단거리의 경로들이 가장 먼저 나오기 때문에 방문 처리가 안된 경로들만 저장했다가 그 사이즈와 결과를 출력하..

union find 자료구조에 해쉬맵을 사용해서 푸는 문제이다. Fred Barney Barney Betty Betty Wilma 이런 식의 입력이 주어지는데 일반적인 집합 처리로는 문자열을 구분하기 까다롭다. 따라서 해쉬맵에 저장해 각 이름의 번호를 가져와 그 번호로 Union을 해준다. 순서는 다음과 같다. 해쉬맵에서 가져온 번호로 Union 한다. Union 하면서 자신이 포함된 집합의 크기를 증가시킨다. 그 집합의 크기를 출력한다. group(집합) 배열과 node(집합의 크기) 배열은 입력에 따라 위 사진과 같이 변한다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; impor..

전형적인 Union & Find 문제이다. 해당 알고리즘을 알고 있다면 바로 적용해서 풀면 된다. 입력에서 연결되어 있는 점들은 바로 union을 해주고 마지막에 여행 경로가 주어졌을땐 해당 경로들을 받아서 find로 같은 집합에 속해있는지를 판별하면 된다. package Feb_2022; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Boj_1976 { static int N; static int M; static int[] group; publi..

다른 문제와 또오옥같은 다익스트라 문제이다. 1번 출력이야 그냥 최단거리 출력해주면 되는데 2번 3번을 어떻게 할지가 이 문제의 핵심이다. 해결법은 단순히 배열을 만들어 노드의 인덱스에 그 전 노드 번호를 넣어주고 그 후에 그 순서를 역으로 따라가면서 arrayList에 넣어준다. 그 후 2번 출력에 대해 arrayList의 size를 출력해주고 3번 출력에 대해 arrayList를 출력해주면 끝이다. package Feb_2022; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import ..

모든 정점 사이의 최단거리가 우선 필요하다. 따라서 다익스트라를 N번 하거나 플로이드를 돌리면 되는데 나는 다익스트라를 연습중이어서 그냥 다익스트라를 N번 돌리는 방향으로 정했다. 최단거리를 가기 위해 거쳐야하는 첫번째 지점을 출력하는 문제이다. 우선 기본적으로 다 자기 자신에 대한 정점 번호를 가지고 있다가 최단 거리를 탐색하면서 이전 정점의 번호를 가지는 방법을 취했다. 하지만 1번에서 2번으로 갈 경우 그럼 2번 정점은 최단거리를 위해 1번 정점을 가지는 예외가 발생하기 때문에 그것에 대한 처리를 해주면 끝이다. package Feb_2022; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamRe..

정말 다익스트라 알고리즘의 기초 문제이다. 따로 생각할것 없이 다익스트라 알고리즘을 사용하면 풀린다. package Feb_2022; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.PipedInputStream; import java.util.ArrayList; import java.util.Arrays; import java.util.PriorityQueue; import java.util.StringTokenizer; public class Boj_1916 { static int N; static int M; public static class Point ..

어떤 정점 A에서 B를 거쳐 A로 다시 돌아오는 최단거리를 구하는 문제이다. 결국 A에서 B를 향한 최단거리 + B에서 A를 향한 최단거리이기 때문에 다익스트라를 두번 돌려주면 된다. 4번까지의 정점이 있고 거쳐야하는 정점이 2번이라면 1번은 2번을 거쳐 2번에서 1번을 가는 최단거리 2번은 continue 3번은 2번을 거쳐 2번에서 3번을 가는 최단거리 4번은 2번을 거쳐 2번에서 4번을 가는 최단거리 이렇게 구해진 최단거리중 가장 큰 값을 찾아주면 정답이 된다. package Feb_2022; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayL..