본문 바로가기

Algorithm221

[백준] 15681: 트리와 쿼리 - JAVA https://www.acmicpc.net/problem/15681 풀이트리에 속한 간선의 정보가 주어지고, 루트의 번호가 주어진다. 트리의 정점을 포함해 자신보다 하위에 있는 정점들의 개수를 구하는 문제이다. 먼저 간선의 정보를 인접리스트에 담았다. 루트의 번호부터 dfs탐색을 통해 진행하는데 정점의 개수의 최대값이 크다보니 매번 구하면 시간 초과가 발생할 것 같았다. dp배열을 만들어 dfs탐색을 하며 dp에 저장하고 반환하는 식으로 구현했다.  메모리: 77800KB시간: 812ms 언어: Java 11import java.io.*;import java.util.*;public class Main { static ArrayList> tree; static int[] dp; stati.. 2024. 5. 13.
[백준] 2146: 다리 만들기 - JAVA https://www.acmicpc.net/problem/2146 풀이그래프 탐색 문제. 서로 다른 두 개의 섬을 연결하는 다리의 최솟값을 구해야 한다. 섬은 1, 바다는 0으로 주어져서 섬들을 구분하기 위한 작업을 우선 거쳤다. 섬마다 번호를 하나씩 부여하고 bfs탐색을 통해 해당 번호를 마킹했다. 그 후 섬들끼리 거리를 bfs탐색을 통해 구했다. 처음 제출에 메모리 초과가 났었다. 섬을 구분하는 함수를 구현할 때 번호가 다른 것으로 방문처리가 된다고 생각하여 방문처리하는 boolean배열을 따로 만들지 않았는데, 방문처리 배열을 도입하여 쓸데없는 동작을 제거해주니 메모리초과가 해결되었다.  메모리: 295940KB시간: 1456ms언어: Java 11import java.io.*;import java.. 2024. 5. 13.
[백준] 1005: ACM Craft - JAVA https://www.acmicpc.net/problem/1005 풀이위상정렬을 이용해 건물을 건설하는 시간을 구하는 문제. 어떤 건물을 짓기 위해 우선적으로 지어져야 할 건물이 있다. 특정 번호의 앞에 지어져야할 건물이 여러개가 있다면 그중 가장 오래걸리는 것이 끝난 후 지을 수 있게 된다. 따라서 걸리는 시간을 오름차순으로 하기 위해 우선순위큐를 이용했다. 목표한 건물에 도달했으면 시간을 출력하면 끝.  메모리: 245956KB시간: 864ms언어: Java 11import java.io.*;import java.util.*;public class Main { static class Node implements Comparable { int num; int time; .. 2024. 5. 13.
[백준] 13418: 학교 탐방하기 - JAVA https://www.acmicpc.net/problem/13418 풀이MST를 구해 오르막길의 개수를 찾는 문제였다. 오르막길을 가중치가 0, 내리막길은 1로 주어지는데 오르막길을 최대로 이용한 경우, 최소로 이용한 경우를 각각 구해야 한다. 오르막길의 가중치가 0이므로 가중치가 작은순으로 프림 알고리즘을 구현하면 최대로 이용한 개수를 구할 수 있고, PriorityQueue의 정렬 조건을 내림차순으로 해주면 오르막길을 최소로 이용한 개수를 구할 수 있다.  메모리: 191972KB시간: 1292ms언어: Java 11import java.io.*;import java.util.*;public class Main { static class Node { int point; .. 2024. 5. 13.
[백준] 1774: 우주신과의 교감 - JAVA https://www.acmicpc.net/problem/1774 풀이최소 신장 트리를 구하는 문제이다. 정점을 다 연결해야 하는데 이미 연결된 선이 주어진다. 이미 연결된 선은 가중치를 0으로 두고 계산했다. 크루스칼과 프림 알고리즘이 있는데 프림 알고리즘을 사용해봤다. 프림 알고리즘은 하나의 정점에서 연결된 간선들 중에서 하나씩 선택하면서 최소신장트리를 찾는 알고리즘이다     1. 임의 정점을 하나 선택해서 시작한다.     2. 선택한 정점과 인접하는 정점들 중 최소 비용의 간선과 연결된 정점을 선택한다.     3. 모든 정점이 선택될때까지(정점의 개수 - 1개의 간선이 선택될때까지) 1, 2번과정을 반복한다. pq에 방문하지 않은 점들을 넣고 가중치가 작은 순으로 PriorityQueue를 이.. 2024. 5. 13.
[백준] 21924: 도시 건설 - JAVA https://www.acmicpc.net/problem/21924 풀이도로를 연결해야 한다. 최소한의 비용으로. 즉, 최소 스패닝 트리(MST)에 대한 문제이다. 크루스칼과 프림의 두 가지 알고리즘으로 풀 수 있는데 크루스칼 알고리즘을 선택했다. 크루스칼 알고리즘은 간선을 하나씩 선택해서 최소신장트리를 찾는 알고리즘이다.     1. 처음에 모든 간선을 가중치에 따라 오름차순으로 정렬하고 시작한다.     2. 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킨다.(이때, 사이클이 존재하게 될 경우 다음으로 가중치가 낮은 간선을 선택한다.)     3. N-1개의 간선이 선택될때까지 2번 과정을 반복한다. 간선을 비용에 따라 정렬해야 하는데 정렬하는 방법으로 PriorityQueue를 이용했다. 크.. 2024. 5. 13.
[백준] 11779: 최소비용 구하기 2 - JAVA https://www.acmicpc.net/problem/11779 풀이출발 도시부터 도착 도시까지 최소 비용으로 가야한다. 다익스트라 알고리즘을 사용하는 문제였다. 최소 비용, 경로에 포함된 도시의 개수, 방문한 도시를 출력해야 했다. 다익스트라 알고리즘으로 최소 비용을 구하고, int 배열로 비용을 저장하지 않고 class 배열을 만들어서 이전의 도시와 비용을 저장해줬다. 최소 비용을 구한 뒤 도착지부터 역추적하여 방문한 경로를 구했다. 역추적 하기 위해 class를 만들어 배열에 넣어준 것이다.  메모리: 54432KB시간: 576ms언어: Java 11import java.io.*;import java.util.*;public class Main { static class Node imple.. 2024. 5. 13.
[백준] 24230: 트리 색칠하기 - JAVA https://www.acmicpc.net/problem/24230 풀이트리가 주어지고 트리를 주어진 색으로 칠해야 한다. 한 정점에 색을 칠하면 그 정점의 하위 정점들 모두에게 같은 색을 칠한다. 따라서 루트인 1번 정점부터 시작하여 아래로 내려가면서 색이 다르면 색을 칠해줬다. dfs탐색을 통해 먼저 자식의 부모의 색을 따라서 칠하고 원하는 색과 비교하여 색을 다시 칠했다.  메모리: 111952KB시간: 1684ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int N, ans; static int[] arr, color; static ArrayList> list; static boolean.. 2024. 5. 13.
[백준] 16947: 서울 지하철 2호선 - JAVA https://www.acmicpc.net/problem/16947 풀이서로 연결된 정점들의 번호가 주어진다. 루프를 이루고 있는것을 먼저 찾고 그 루프로부터의 거리를 출력해야한다. dfs탐색을 통해 루프를 탐색했다. 저장된 루프의 정점으로부터 bfs탐색을 통해 루프에 포함되지 않은 정점들이 루프로부터 얼마나 떨어져 있는지 저장하고 출력한다.  메모리: 25788KB시간: 388ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int N; static ArrayList> list; static boolean[] loop; static int[] dist; public static void ma.. 2024. 5. 13.
[백준] 11559: Puyo Puyo - JAVA https://www.acmicpc.net/problem/11559 풀이같은 색 블럭이 4개 이상 연결되어 있으면 한번에 없어진다. 한 라운드씩 진행하여 없어질 수 있는 블럭이 있으면 1연쇄 늘어나고 다음 라운드로 넘어갔다. 라운드를 넘어가기 전에 블럭들을 없앤 후 밑으로 내려주는 작업도 필요했다. 이차원 배열을 탐색하여 '.'이 아닌 경우 bfs탐색을 진행했다. 상하좌우에 같은 색이 있으면 list에 담고 queue에 넣어 계속했다. list에 담긴 개수가 4이상이면 '.'으로 없애주었다. 이번 라운드에 없어진 블럭이 있으면 내려주는 작업을 해야한다. 내려줄때는 열을 먼저 탐색하여 해당 열의 블럭들을 stack에 담아 아래에서부터 채워줬다.  메모리: 14480KB시간: 128ms언어: Java 11i.. 2024. 5. 13.

티스토리툴바