1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 최소 신장 트리(Minimum Spanning Tree)를 구하는 문제로 크루스칼 알고리즘과 프림 알고리즘으로 구현해보았다. 크루스칼 알고리즘 : 최소 신장 트리(MST)를 찾는 알고리즘 신장 트리란 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 조건이 gangintheremark.tistory.com ..
11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 244ms 벨만 포드 알고리즘 특정 노드(1번 노드)에서 모든 노드로 가는 가장 빠른 시간을 순서대로 출력하는 문제로 최단 경로를 계산하는 문제이다. 그리고 이 문제에서는 가중치가 음수의 값을 가지므로 다익스트라가 아닌 벨만 포드 알고리즘으로 최단 경로를 계산한다. 음의 가중치 순환으로 시간을 무한히 오래 전으로 되돌릴 수 있으면 -1 출력해야 하므로 전체 간선을 확인하며 최단 거리 테이블 d 를 갱신한..
17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 120ms DFS BFS 부분집합 이 문제는 두 개의 선거구로 나누는데 같은 선거구끼리는 서로 인접해야 한다. n개의 구역들을 2개의 선거구로 나누기 ➜ 부분집합 DFS 각각의 선거구 구역들끼리 서로 인접한지 확인 ➜ BFS 두 개의 선거구로 나누는 작업은 부분집합으로 한 선거구에는 반드시 하나의 구역이 포함되어야 한다. private static void divide(int idx) { if (idx == N) { a.clear(); b.clear(); for (int i = 0; ..
1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 728ms 다익스트라 방향 그래프가 주어지고 출발 노드에서 모든 노드로의 최단 경로를 구하는 문제로 최소힙을 이용한 다익스트라 알고리즘을 구현하면 된다. # 소스코드 import java.io.*; import java.util.*; public class Main { static class Node implements Comparable { int index; int distance; public Node(int index..
11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 368ms 플로이드 워셜 인접행렬 모든 노드에서 다른 모든 노드까지의 최단 비용을 찾는 문제로 노드의 범위(N≤100)가 작아 플로이드 워셜 알고리즘을 이용한다. 이 문제에서 주의해야 할 점은 입력값으로 중복된 출발도시와 도착도시가 들어올 수 있다는 점 갈 수 없는 곳은 0으로 출력해야 한다는 점 따라서 처음 입력을 받을 때, 출발노드에서 도착노드로 가는 비용이 더 작은 것을 이차원 테이블에 넣어줘야한다. 또한 모든 노드를 INF 로 초기화 후 구현하기 때문에 마..
1066ms 순열 부분집합 DFS 양팔저울에 왼쪽 또는 오른쪽에 무게 추를 하나씩 올리는데 추를 올리는 과정에서 오른쪽이 왼쪽보다 무거워지면 절대 안된다는 것이 조건이다. 즉 추를 올리는 순서와 어느 쪽 저울에 추를 올릴지 고려해야한다. 추를 올리는 순서를 정하는 것은 순열, 올리는 순서가 정해진 추들을 어느쪽에 올릴 것인지 정하는 것은 부분집합을 이용하여 구현하였다. 추의 순서를 정한 후 부분집합을 통해 추들을 올렸을 때, 오른쪽무게가 왼쪽무게보다 커지지 않고 모든 추를 다 올렸으면 결과값++ 문제가 헷갈릴 수 있어 꼼꼼하게 읽어봐야 이해하는 문제였다. 순열과 부분집합을 함께 이용하는 문제로 되게 괜찮은 문제라고 생각이 든다 # 소스코드 import java.io.BufferedReader; impor..
149ms 빡구현 BFS 문자에 따라 명령어를 실행시켰을 때, 프로그램 종료 문자인 @ 까지 도달할 수 있는가 없는가에 대해 확인하는 문제이다. 이 문제에서 중요하게 고려해야 할 점은 ? 문자는 4방향 중 어느 방향으로 갈 것인가 프로그램이 종료하지 않는 케이스면 어떻게 종료하지 않은 것을 판단할 것인가 두 가지만 신경쓴다면 복잡하지만 빡구현으로 해결할 수 있다. ? 문자를 만났을 때, 각각의 방향에 따라 경우의 수를 따져야하므로 BFS로 구현하였다. 또한 프로그램이 종료되지 않는 케이스를 판단하기 위해 (행, 열, 방향, 메모리)의 방문체크를 해주는 4차원 배열이 필요하다. (x,y)좌표와 방향, 메모리에 방문체크가 되어있다면 계속 루프를 돌고 있는 것으로 프로그램이 종료할 수 없는 경우이다. 그래서 ..
190ms 구현 BFS 최소의 클릭으로 지뢰를 제외한 모든 칸의 숫자들을 표시하는 문제이다. 핵심은 주변에 지뢰가 없는 칸은 8방향의 칸을 클릭없이 확인할 수 있다는 것이다. 즉, 클릭한 칸을 중심으로 가지가 뻗어나가는 구조로 BFS로 해결하였다. 먼저 주변에 지뢰가 없는 칸을 우선적으로 클릭한 후, 방문처리가 되지 않고 주변에 지뢰가 하나라도 있는 나머지 칸 수를 클릭 수에 더해주면 된다. 1. 각 좌표에서 주변에 지뢰가 몇 개 있는지 체크 ➜ 주변에 지뢰가 몇 개 있는지는 중요한 부분이 아니므로 지뢰가 있으면 1, 지뢰가 없으면 0 으로 저장 2. 주변에 지뢰가 없는 칸(0)을 중심으로 BFS를 실행하며 주변 칸들을 방문처리 해준다. 3. 방문하지 않았으며 주변에 지뢰가 있는 칸(1)은 무조건 한 번..
155ms 간단하게 생각하기 !! 이 문제의 핵심은 입력 중 손님들이 오는 시간은 오름차순으로 주어지지 않는다. 따라서 먼저 Arrays.sort() 를 통해 정렬해준다. 먼저 오는 손님들 부터 탐색하며 손님이 온 시간일 때, 1. 붕어빵을 몇 개 만들 수 있는지 구하기 2. 앞의 손님들의 수(i) 빼줬을 때 0보다 작으면 제공할 붕어빵이 없다는 것 int dessert = (arr[i] / m) * k; if (dessert - i
123ms 구현 부분집합 DFS 이 문제는 가로로 연속된 M개의 칸에서 채취할 수 있는 꿀의 최대 양(C)을 넘지 않으면서 최대한 많은 꿀의 양을 채취할 수 있는 두 구간을 찾아내는 문제이다. 이 문제의 핵심은 두 구간이 겹치면 안된다 → 즉, M개의 칸 중 일부칸만 이용했더라도 M개의 칸 전체와 겹치면 안됨 연속된 M개의 칸을 선택한 후 채취할 꿀 칸을 선택하는 건 연속하지 않아도 된다 (아래그림 참조) 행마다 최대수익을 얻는 경우를 찾은 후, 그 중 최대수익이 가장 큰 행을 찾아 그 값을 결과에 더하고 다시 그 행만 최대수익을 구해준다. (단, 이전에 선택된 칸은 제외) 다시 행마다 최대수익이 가장 큰 행을 찾아 결과에 더해주며 해결하였다. 조건에 맞게 구할 수 있는 조합에서 최대 수익을 얻는 경우 ..
구현 DFS 달마다 1일 이용권 / 1달 이용권 / 3달 이용권 / 1년 이용권을 쓸 때, 가작 적은 비용으로 일년동안 수영장을 이용할 수 있는 경우를 찾아 비용을 출력하는 문제이다. 1년 이용권은 달마다 탐색할 필요가 없어 미리 result 에 1년 이용권 요금을 넣어둔 후, 1일/1달/3달이용권을 달마다 DFS를 통해 탐색해보고 최소비용을 찾아 result와 비교한 후 답을 출력하였다. dfs(m + 1, sum + price[0] * year[m]); dfs(m + 1, sum + price[1]); dfs(m + 3, sum + price[2]); DFS를 이용하면 쉽게 해결할 수 있는 문제였다. #소스코드 import java.io.BufferedReader; import java.io.File..
구현 길이가 K인 마름모 모양의 영역 내에 존재하는 집들이 있을 때, (운영비용) - (집이 지불하는 비용) * (집의 수) 가 양수이면서 집의 수가 최대일 때를 찾으면 된다. K는 1부터 전체 영역을 포함할 수 있는 길이인 N * 2 까지 가능하며 K 길이와 좌표에따라 완전탐색으로 해결할 수 있는 문제이다. 로직은 생각하기 쉬우나 마름모 모양의 영역 내에 집이 존재하는가에 대한 체크하는 과정에서 어려움이 있었다. 마름모의 중심을 기준으로 반지름이 k인 원을 생각해주면 된다. 즉, 중심 좌표와 집의 좌표까지 거리가 k보다 작으면 마름모 영역 내에 존재한다는 것을 의미한다. Math.abs(house[0] - i) + Math.abs(house[1] - j) < k 마름모 시렁 # 소스코드 import j..
