🏷️ 카테고리
`#그래프` `#깊이 우선 탐색` `#다이나믹 프로그래밍`
⏳ 시간복잡도
`O(N)`
📒 해설
문제를 이해하고, 접근하는 과정에서 헷갈릴 수 있었는데, 운이 좋게도 빠르게 정답에 가까운 풀이를 떠올릴 수 있었습니다. 초기에 떠올린 방식은 `위상 정렬`이었는데, 아마 해당 방법을 통해서도 풀이는 가능할 것입니다. 해당 문제에서의 핵심은 섬 A를 파괴하는 비용과 섬 A와 연결된(Leaf 쪽으로) 섬들을 각각 부수는 비용 중에서 더 최소값을 선택하는 것입니다.
📜 문제 조건
문제의 입력 조건은 다음과 같습니다.
- 테스트 케이스 T에 대해서 `1 <= T <= 100`이 주어진다.
- 섬의 총 개수 N은 `1 <= N <= 1000`이다. 다리 수 M은 주어진 형태가 MST 형태이기 때문에, `N-1`이다.
- 각 다리를 폭파하는 비용 D는 `1 <= D <= 20`이다.
Worst 케이스를 고려해서 테스트 케이스가 100개가 나타났을 때, 한 테케의 연산 횟수는 100만 회 안에 끝나야 한다는 것을 알 수 있습니다.
🔍 문제 접근
이 문제를 풀기 위해서 가장 중요한 것은 앞서 언급한 최소값을 구한다는 아이디어입니다. 저는 이 방법을 구현하기 위해서 그래프를 만들고, 1번 섬부터 연결된 섬을 부수는 비용 vs leaf 섬을 부수는 비용 중 최소 값을 재귀적인 형태로 찾았습니다.
아래 사진으로 보면 5번을 부수는 비용인 4와 leaf 섬을 부수는 비용의 합인 3(1+2) 중에서 더 작은 값인 3을 구하는 방법입니다. 해당 방법에 대해서 한번 고민해 보시고, 아래 풀이를 살펴보겠습니다.
🔑 문제 풀이
사용 변수
사용한 변수 중 중요한 값은 아래에 2개인 그래프를 구성한 `Edge`의 배열과, 간선을 탐색하며 자식 정점(leaf랑 가까운 쪽)으로 이동하기위해 필요한 방문 배열입니다.
static Edge[] graph; // 연결 리스트 형태의 그래프
static boolean [] visited; // 방문 체크 배열, 양방향이기 때문에 필요
static class Edge { // 그래프를 이루기 위한 자료구조
int to;
int cost;
Edge next;
public Edge(int to, int cost, Edge next) {
this.to = to;
this.cost = cost;
this.next = next;
}
}
섬 파괴 비용 계산 DFS
아래 함수는 나를 부수는 비용 vs 내 자식들을 부수는 비용을 구하는 코드입니다.
여기서 나를 부수는 비용은 반복문 속 `e.cost`이고, 자식들을 부수는 비용은 `dfs(e.to)` 입니다. 둘 중 더 작은 값을 더해서 이를 리턴합니다.
첫 번째 주어진 그림을 다시 생각해 보면, 1번이 2번과 5번을 부수는 최솟값들의 합만큼 비용을 낸다고 생각하시면 될 것 같아요. 처음에 말했던 것처럼, 최솟값을 구하는 아이디어를 구현만 한다면 끝입니다!
static int dfs(int i) {
boolean isLeafNode = true; // 리프 노드인지 체크
int cost = 0;
for (Edge e = graph[i]; e != null; e = e.next) { // 연결 리스트 순회
if(visited[e.to]) continue; // 이미 방문한 배열은 PASS
isLeafNode = false; // 한번이라도 다른 노드로 간다면 리프 노드가 아니다.
visited[e.to] = true;
int dfs = dfs(e.to);
int value = Math.min(e.cost, dfs); // 내 자식 노드들을 부수는 최소 값 vs 나를 부수는 값
cost += value;
}
if(isLeafNode) return graph[i].cost; // leaf노드라면 그냥 자신을 부수는 비용 리턴, 별로 중요하지는 않음.
return cost;
}
전체 코드
import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
static Edge[] graph;
static boolean [] visited;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
int T = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
for (int i = 0; i < T; i++) {
st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
graph = new Edge[n+1];
visited = new boolean[n+1];
for(int j = 0; j<m; j++){
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int cost = Integer.parseInt(st.nextToken());
graph[a] = new Edge(b, cost, graph[a]);
graph[b] = new Edge(a, cost, graph[b]);
}
visited[1] = true;
int cost = 0;
if(m != 0)
cost = dfs(1);
sb.append(cost).append("\n");
}
System.out.println(sb);
}
static int dfs(int i) {
boolean isLeafNode = true;
int cost = 0;
for (Edge e = graph[i]; e != null; e = e.next) {
if(visited[e.to]) continue;
isLeafNode = false;
visited[e.to] = true;
int dfs = dfs(e.to);
int value = Math.min(e.cost, dfs);
cost += value;
}
if(isLeafNode) return graph[i].cost;
return cost;
}
static class Edge{
int to;
int cost;
Edge next;
public Edge(int to, int cost, Edge next) {
this.to = to;
this.cost = cost;
this.next = next;
}
}
}
결과
