본문 바로가기
반응형

알고리즘113

백준 1976번 : 여행 가자 java 이 문제는 분리 집합을 이용하여 푸는 문제입니다. 분리 집합이란 여러 개의 분리된 집합들이 있을 때 이 집합들에 대한 연결 관계를 입력받아 연결하여 이를 이용하는 문제입니다. 이 문제에서는 N개의 도시에 대한 연결 관계를 입력받아서 M개의 도시를 여행할 수 있는지 확인하는 문제입니다. 한번 갔던 도시라도 연결되어 있기만 하다면 갈 수 있습니다. 코드를 바로 보여드리도록 하겠습니다. import java.io.*; import java.util.*; public class Main { static int[] parent; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new In.. 2022. 6. 29.
백준 20040번 : 사이클 게임 java 이 문제는 분리 집합을 이용하여 푸는 문제입니다. 첫 번 째 줄에서 N과 M을 받은 후 N개의 정점에서 M개의 선을 이을 때 사이클이 생기지 않으면 0을 출력하고 사이클이 생기면 사이클이 생겼을 때 입력받은 간선의 수를 출력하는 문제입니다. 예제 1번은 모든 간선을 이어도 아래와 같이 사이클이 없으므로 0을 출력합니다. 하지만 예제 2번은 중간에 사이클이 생깁니다. 언제 사이클이 생기는지 보여드리겠습니다. 첫 번째 간선을 입력받았을 때 다음과 같은 모습입니다. 두번째 입력을 받았을 때 위와 같은 모습입니다. 세번째 입력을 받았을 때 다음과 같은 모습입니다. 그리고 네번째 입력을 받을 때 사이클이 생깁니다. 따라서 4를 출력합니다. 이 문제를 풀면서 그래프가 생기는가 생기지 않는가는 union-find 함.. 2022. 6. 29.
백준 1261번 : 알고스팟 java 이 문제는 벽을 최대한 적게 부수면서 (1, 1)에서 (N, M)까지 갈 때 부순 벽의 개수를 출력하는 문제입니다. 이 문제를 언뜻 보았을 때 dfs를 이용해서 벽을 부수면서 탐색해야 할 것처럼 보입니다. 하지만 이 문제는 끝까지 갔을 때 부순 벽의 개수가 최소가 되어야합니다. 따라서 bfs를 이용해서 주변을 탐색하며 끝까지 가장 벽을 적게 부수고 가는 경우의 수를 찾아야 합니다. 이를 위해서 PriorityQueue에 각각의 노드의 정보와 벽을 몇 개를 부수었는지에 대한 정보를 넣고 벽을 부신 개수를 오름차순으로 정렬하여 벽을 가장 적게 부수고 끝 점까지 가는 방법을 찾아야 합니다. 이에 대한 코드를 보여드리도록 하겠습니다. import java.io.*; import java.util.*; publi.. 2022. 6. 27.
백준 1068번 : 트리 java 이 문제는 트리를 이용하는 문제로 트리를 만들고 노드를 추가, 삭제한 다음 리프 노드의 개수를 세는 문제입니다. 이 문제를 풀 때 조심해야하는 점은 0번이 아닌 다른 노드가 루트 노드가 될 수 있고 이진트리라는 말이 없기 때문에 자식 노드가 3개 이상일 수 있다는 것입니다. 이러한 점 때문에 이 문제에서 쓸 트리를 배열에 저장하는 방식을 통해서 만들었습니다. parent 배열은 만들어 자신의 부모 노드를 저장할 배열을 만든 후 노드가 제거되면 그 자식 노드까지 제거되도록 dfs를 이용하였습니다. 코드를 바로 보여드리겠습니다. import java.io.*; import java.util.*; public class Main { static int N; static int[] parent; static b.. 2022. 6. 26.
백준 16236번 : 아기 상어 java 이 문제는 bfs를 이용해서 아기 상어가 엄마 상어에게 도움을 받지 않고 얼마나 물고기를 먹으러 이동할 수 있는지를 구하는 문제입니다. 이 문제의 초기 조건은 아래와 같습니다. 아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다. 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다. 여기서 아기 상어가 상하좌우로 1칸씩 이동할 수 있다는 것에서 bfs를 사용할 수 있을 것이라는 생각을 했습니다.. 2022. 6. 25.
백준 1504번 : 특정한 최단 경로 java 이 문제는 다익스트라 알고리즘을 이용하여 중간에 정점 v1과 v2를 거쳐 N으로 갈 때의 최단 경로의 길이를 구하는 문제입니다. 이 문제를 풀기 위해서는 우선 정점 1에서 v1과 v2로 갈 때의 최단 경로의 길이를 구해야 합니다. 만약 경로가 존재하지 않을 경우에는 그다음 단계를 진행하지 않아도 됩니다. 1에서 v1으로 가는 경로가 없다고 가정하면 1에서 v2로 가는 최단 경로를 구하고 그 후 v2에서 v1으로 가는 최단 경로를 구해야 합니다. v2와 v1을 모두 거쳐야 하기 때문에 이 경로를 구해줍니다. 그리고 마지막으로 v1에서 N으로 가는 최단 경로를 구한 후 이 3개의 경로의 길이를 더한 값을 출력합니다. 이에 대해서 예제 1번을 예시로 설명드리겠습니다. 위 그림은 예제 1번을 나타낸 그림입니다... 2022. 6. 25.
백준 2589번 : 보물섬 java 이 문제는 bfs를 이용하여 섬 안에서 가장 먼 거리에 보물을 묻을 때 보물 간의 거리를 구하는 문제입니다. 이 문제를 풀 때는 브루트포스 알고리즘을 사용해야 합니다. 지도의 각 칸을 탐색하면서 탐색한 칸이 땅일 때 연결된 땅들을 전부 탐색하면서 가장 거리가 먼 땅을 찾습니다. 코드를 보면서 조금 더 설명드리도록 하겠습니다. import java.io.*; import java.util.*; public class Main { static int row, col; static char[][] map; static int[] dR = {1, -1, 0, 0}; static int[] dC = {0, 0, 1, -1}; static int max = 0; public static void main(Strin.. 2022. 6. 24.
백준 1238번 : 파티 java 이 문제는 다익스트라 알고리즘을 이용하여 학생들이 파티를 참가하기 위해 한 마을로 모였다가 다시 자신의 마을로 돌아갈 때 가장 시간이 오래 걸리는 학생의 소요시간을 구하는 문제입니다. 이 문제를 푸는 방법은 2가지가 있습니다. 우선 첫 번째의 방법은 플로이드 와샬 알고리즘을 이용하여 각각의 학생들이 오고 갈 때의 시간을 구하는 방법이 있습니다. 하지만 이 방법을 사용한다면 시간 복잡도가 O(n^3)이 되어 시간이 오래 걸리게 됩니다. 이 문제에서는 플로이드 와샬 알고리즘을 써도 맞다고는 나오지만 N이 더 늘어나면 시간이 메모리를 더 많이 쓰게 되므로 좋은 정답이 아닙니다. 우선 플로이드 와샬 알고리즘으로 이 문제를 풀었을 때를 보여드리겠습니다. import java.io.*; import java.uti.. 2022. 6. 24.
반응형

티스토리툴바