PS(Problem Solving)/BOJ244

• [백준/BOJ] 1504번: 특정한 최단 경로 문제 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 해설 다익스트라 알고리즘을 응용하는 문제이다. 문제에는 다음과 같은 조건이 있다. 임의로 주어진 두 정점은 반드시 통과해야 한다. 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 주어진 두 정점을 거쳐야 하는 최단 경로를 구해야 한다. 간단히 생각해보면, 다음과 같다. 1 -> v1 -> v2 -> n 1 -> v2 -> .. PS(Problem Solving)/BOJ 2022. 8. 5.

• [백준/BOJ] 2887번: 행성 터널 문제 https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 해설 모든 행성을 연결했을 때, 필요한 최소 비용을 구하는 문제이므로 크루스칼 알고리즘을 사용하였다. 처음 도전했을 때는 행성 간의 거리를 이중 반복문을 이용해 모두 계산하여 풀었다. 하지만 이렇게 할 시 이중 반복문에서 O(n2)이고, n의 범위가 10만이기 때문에 메모리 초과가 발생하였다. 이를 해결하기 위해 모든 행성을 비교하지 않고 두 행성간 가장 작은.. PS(Problem Solving)/BOJ 2022. 8. 4.

• [백준/BOJ] 1238번: 파티 문제 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 해설 문제의 핵심을 찾아보면 다음과 같다. 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 최단 시간에 오고 가기를 원한다. 단방향이기 때문에 오고 가는 길이 다를지도 모른다. 최단 시간을 구하는 문제이기에 다익스트라 알고리즘을 이용하면 된다. 파티를 갔다가, 다시 집에 돌아오는 시간까지 계산해야 하기 때문에, 각 노드 당 2번.. PS(Problem Solving)/BOJ 2022. 8. 4.

• [백준/BOJ] 1854번: K번째 최단경로 찾기 문제 https://www.acmicpc.net/problem/1854 1854번: K번째 최단경로 찾기 첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이어지는 m개의 줄에 www.acmicpc.net 해설 다익스트라 알고리즘을 이용해서 풀 수 있는 문제이다. 이 문제에서는 각 노드마다 우선순위 큐를 두어 이 노드를 방문할 때마다의 시간을 저장할 것이다. val time = Array(cityCnt + 1) { PriorityQueue(reverseOrder()) } 이 때, 큰 수가 top에 오도록 해야 한다. 즉 내림차순이어야 한.. PS(Problem Solving)/BOJ 2022. 8. 3.

• [백준/BOJ] 1916번: 최소비용 구하기 문제 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 해설 A번째 도시에서 B번째 도시로 가는데 필요한 최소 비용을 구하는 문제이다. 따라서 다익스트라 알고리즘을 사용하면 된다. 한 도시에서 다른 도시로 가는 버스는 다시 돌아오지 않으므로 단방향이다. 따라서 다익스트라를 진행하기 위한 그래프를 설정할 때 양방향이 아닌 단방향으로 비용을 저장해주면 된다. 다익스트라를 다 수행하고 특정 도시까지 최소 비용을 출력해.. PS(Problem Solving)/BOJ 2022. 8. 3.

• [백준/BOJ] 1753번: 최단경로 문제 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 해설 다익스트라 알고리즘을 사용하여 해결할 수 있는 문제이다. 문제에서 방향그래프가 주어진다고 되어있다. 따라서 단방향으로만 그래프를 설정해주면 된다. 다익스트라 알고리즘을 잘 모른다면 다익스트라 알고리즘 글을 읽어보면 이 문제를 쉽게 풀 수 있을 것이다. 소스 코드 import java.util.* import kotlin.collections.Arra.. PS(Problem Solving)/BOJ 2022. 8. 3.

• [백준/BOJ] 15686번: 치킨 배달 문제 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 해설 브루트 포스(Brute Force) 문제이다. 문제에서 원하는 것은 결국, 모든 집에 대해 가장 가까운 치킨집까지의 거리의 합이다. 내가 푼 문제 해결 과정(알고리즘)은 다음과 같다. 맵을 입력받으면서, 집과 치킨집의 좌표를 저장해둔다. 모두 저장했다면, dfs를 수행하며 남길 치킨집을 선택한다. visited 배열을 방문처리를 해준 후의 갯수를 세고, 이를 다시 .. PS(Problem Solving)/BOJ 2022. 8. 2.

• [백준/BOJ] 1368번: 물대기 문제 https://www.acmicpc.net/problem/1368 1368번: 물대기 첫 줄에는 논의 수 N(1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다. 다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어 www.acmicpc.net 해설 논에 물을 대는 방법은 두 가지가 있다. 직접 논에 우물을 판다. 이미 물을 대고 있는 다른 논으로부터 물을 끌어온다. 즉, 논에 우물을 파는 비용과 논 사이를 연결하는 하는 비용을 비교해야 하는 문제이다. 어렵게 생각할 것 없이, 우물을 파는 비용을 담는 정보도 간선에 추가해주면 된다. 즉, 노드를 한개 더 만든다 생각하면 된다. 예를 들어, 문제의 예시.. PS(Problem Solving)/BOJ 2022. 8. 1.

• [백준/BOJ] 2589번: 보물섬 문제 https://www.acmicpc.net/problem/2589 2589번: 보물섬 첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 www.acmicpc.net 해설 bfs를 사용해서 문제를 해결할 수 있다. 처음 봤을 때는 두 곳에 나뉘어 묻혀있다길래, 꽤 복잡한 문제인 줄 알았으나, 육지인 곳마다 bfs를 실행시켜 가장 긴 값을 찾으면 되는 단순 bfs 문제였다. 해설 import java.util.* private var row = 0 private var col = 0 private val dx = intArrayOf(1, -1, 0, 0) pr.. PS(Problem Solving)/BOJ 2022. 7. 31.

• [백준/BOJ] 1774번: 우주신과의 교감 문제 https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 문제 최소 비용을 구해야 하기 때문에, MST 알고리즘을 사용하는 문제이다. 따로 어떤 노드부터 시작해라라는 말이 없으므로 크루스칼 알고리즘을 사용하였다. 황선자씨는 이미 교감하고 있는 우주신들이 있다. 따라서 우선적으로 이미 교감하고 있는 우주신들을 union을 통해 합집합 연산을 해준다. 이후 아직 연결되지 않은 우주신들과의 거리를 구하여 우선순위 큐에 시작점,.. PS(Problem Solving)/BOJ 2022. 7. 30.

• [백준/BOJ] 10423번: 전기가 부족해 문제 https://www.acmicpc.net/problem/10423 10423번: 전기가 부족해 첫째 줄에는 도시의 개수 N(1 ≤ N ≤ 1,000)과 설치 가능한 케이블의 수 M(1 ≤ M ≤ 100,000)개, 발전소의 개수 K(1 ≤ K ≤ N)개가 주어진다. 둘째 줄에는 발전소가 설치된 도시의 번호가 주어진다. 셋째 www.acmicpc.net 해설 크루스칼 알고리즘을 응용하여 해결할 수 있는 문제이다. 발전소의 개수가 한개라면, 기본적인 크루스칼 알고리즘으로 최소 비용을 구할 수 있다. 하지만 이 문제에서는 발전소의 개수가 여러 개일 수도 있다. 또한 모든 간선이 연결되어야 하는 것이 아니고, 발전소를 통해 전기를 공급받기만 하면 된다. 나는 미리 발전소의 위치를 -1로 해주었다. 이처럼.. PS(Problem Solving)/BOJ 2022. 7. 29.

• [백준/BOJ] 16236번: 아기 상어 문제 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 해설 bfs를 사용하여 현재 상어의 위치에서 모든 물고기들의 위치까지 거리를 구하고, 그 중 가장 거리가 가까운 물고기를 찾는다. 나는 우선 먹을 수 있는 물고기들을 전부 찾아 ArrayList에 위치와 상어와의 거리를 저장해주었다. 저장이 끝났다면 위쪽 좌표부터 시작하여 검사하여 가장 가까운 물고기가 정해지지 않는다면, 왼쪽 좌표를 검사하여 먹으러 갈 물고기를 정한다. 이제 그 위치.. PS(Problem Solving)/BOJ 2022. 7. 29.