[java]학교 탐방하기 - 백준13418
문제
풀이
문제 해석을 하자면,
- 주어진 조건을 만족하는 최악의 경로에서의 피로도와 최적의 경로 간 피로도의 차이를 출력하라.
- 피로도는 오르막길 k^2, 내리막길은 피로도X 이다.
- 출발은 항상 입구(=0) 부터 시작한다.
풀이
- 주어진 그래프는 양방향 그래프이며 최악의 경우는 오르막길을 먼저 선택 하는것이고, 최선의 경우는 내리막길을 먼저 선택하는 것이다.
- 따라서 오름차순, 내림차순을 따로 정렬을 하여 각가 MST를 구하면 최악, 최선을 구할 수 있다.
- MST 문제로 볼 수 있다 -> 크루스칼, 프림 두가지 풀이 방법을 소개
- 프림 알고리즘 -> visited 방문처리를 “큐 삽입시점” 아니라 “큐 poll 시점” 중요
- 크루스칼 알고리즘 -> 합집합 판단 함수를 잘 구현해야 한다.
- 나머지는 주석을 참고하여 코드 확인하자.
코드
프림 알고리즘
static int N, M;
static boolean[] visited;
static List<Pair>[] graph;
static Pair[] outArr1;
static Pair[] outArr2;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(stk.nextToken());
M = Integer.parseInt(stk.nextToken());
graph = new ArrayList[N + 1];
visited = new boolean[N + 1];
outArr1 = new Pair[N + 1];
outArr2 = new Pair[N + 1];
for(int i=0; i<=N; i++) graph[i] = new ArrayList<>();
for (int i = 0; i < M + 1; i++) {
stk = new StringTokenizer(br.readLine(), " ");
int n1 = Integer.parseInt(stk.nextToken());
int n2 = Integer.parseInt(stk.nextToken());
int cost = Integer.parseInt(stk.nextToken());
graph[n1].add(new Pair(n2, cost));
graph[n2].add(new Pair(n1, cost)); //양방향
}
//run
prim();
//debug
// System.out.println(Arrays.toString(outArr1));
// System.out.println(Arrays.toString(outArr2));
//output
int result1=0;
for(int i=1; i<=N; i++){ // 입구 이후부터니까 i=1 부터
if(outArr1[i].cost == 1) continue; // 1은 내리막길 -> PASS
result1 += 1; // 오르막길 개수 추가
}
int result2=0;
for(int i=1; i<=N; i++){
if(outArr2[i].cost == 1) continue; // 1은 내리막길
result2 += 1;
}
System.out.println((int)(Math.pow(result1,2)-Math.pow(result2,2)));
}
static void prim() {
PriorityQueue<Pair> pq = new PriorityQueue<>();
pq.offer(new Pair(0, 0)); // 입구(=0)부터 시작이고 비용도 0으로 봐야한다.
int cnt = 0;
// visited 방문처리를 "큐 삽입시점" 아니라 "큐 poll 시점" 에 하기 때문에,
// 큐에는 중복으로 또 같은 값이 삽입되는 경우가 생긴다.
// 따라서 !pq.isEmpty() 가 아닌 cnt <= N 조건문을 사용하여 "시간을 최적화" 한다.
while (cnt <= N) {
Pair cur = pq.poll();
if(visited[cur.dst]) continue; // 이미 MST 선택되었나 방문체크는 필수
visited[cur.dst] = true; //방문시점 -> MST 선택 시점
outArr1[cnt++] = cur;
for (Pair nxt : graph[cur.dst]) {
if(visited[nxt.dst]) continue; // 이부분 없어도 잘 동작하지만 조금이라도 "시간을 최적화" 위함
pq.offer(nxt); //큐 삽입시점
}
}
// 한번더 새로 init -> outArr2 구하기위해
pq = new PriorityQueue<>((p1, p2) -> {
return p2.cost-p1.cost; //desc
});
visited = new boolean[N + 1];
pq.offer(new Pair(0, 0));
cnt = 0;
while (cnt <= N) {
Pair cur = pq.poll();
if(visited[cur.dst]) continue;
visited[cur.dst] = true; //방문시점
outArr2[cnt++] = cur;
for (Pair nxt : graph[cur.dst]) {
if(visited[nxt.dst]) continue;
pq.offer(nxt); //큐 삽입시점
}
}
}
static class Pair implements Comparable<Pair> {
int dst; int cost;
public Pair(int dst, int cost) {
this.dst=dst; this.cost=cost;
}
@Override
public int compareTo(Pair p) {
return this.cost-p.cost; //asc
}
@Override
public String toString() {
return "Pair{" +
"dst=" + dst +
", cost=" + cost +
'}';
}
}
크루스칼 알고리즘
static int N, M, outSize;
static int[] parent;
static Pair[] edges;
static Pair[] outArr1;
static Pair[] outArr2;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(stk.nextToken());
M = Integer.parseInt(stk.nextToken());
edges = new Pair[M + 1];
parent = new int[N + 1];
outArr1 = new Pair[N + 1];
outArr2 = new Pair[N + 1];
for (int i = 0; i < M + 1; i++) {
stk = new StringTokenizer(br.readLine(), " ");
int n1 = Integer.parseInt(stk.nextToken());
int n2 = Integer.parseInt(stk.nextToken());
int cost = Integer.parseInt(stk.nextToken());
edges[i] = new Pair(n1, n2, cost);
}
//run
kruskal();
//debug
// System.out.println(Arrays.toString(outArr1));
// System.out.println(Arrays.toString(outArr2));
//output
int result1=0;
for(int i=0; i<outSize; i++){ // 입구 이후부터니까 i=1 부터
if(outArr1[i].cost == 1) continue; // 1은 내리막길 -> PASS
result1 += 1; // 오르막길 개수 추가
}
int result2=0;
for(int i=0; i<outSize; i++){
if(outArr2[i].cost == 1) continue; // 1은 내리막길
result2 += 1;
}
System.out.println((int)(Math.pow(result1,2)-Math.pow(result2,2)));
}
static void kruskal() {
// 에지 정렬부터
Arrays.sort(edges, 0, M+1, (o1, o2) -> Integer.compare(o1.cost, o2.cost));
Arrays.fill(parent, -1);
int idx = 0;
for (Pair edge : edges) {
if(isUnion(edge.n1, edge.n2)) continue; // 집합이면 PASS
outArr1[idx++] = edge;
}
Arrays.sort(edges, 0, M+1, (o1, o2) -> Integer.compare(o2.cost, o1.cost));
Arrays.fill(parent, -1);
idx = 0;
for (Pair edge : edges) {
if(isUnion(edge.n1, edge.n2)) continue; // 집합이면 PASS
outArr2[idx++] = edge;
}
outSize = idx;
}
static boolean isUnion(int n1, int n2) {
n1 = find(n1); n2 = find(n2); // root 찾기
if(n1==n2) return true; // 합집합(부모 동일하므로)
if (parent[n1] > parent[n2]) { // n2 부모가 제일 자식이 많다면,
int temp = n1;
n1 = n2; n2 = temp;
} //swap
parent[n1] += parent[n2]; // 자식이 많은쪽에 merge -> 하나의 집합으로 합치려는 의도
parent[n2] = n1; // 부모기록
return false;
}
static int find(int x) {
if(parent[x] < 0) return x; // -1 은 초기값 (자기 자신이 부모)
return parent[x] = find(parent[x]); // root 까지 재귀
}
static class Pair {
int n1; int n2; int cost;
public Pair(int n1, int n2, int cost) {
this.n1=n1; this.n2=n2; this.cost=cost;
}
@Override
public String toString() {
return "Pair{" +
"n1=" + n1 +
", n2=" + n2 +
", cost=" + cost +
'}';
}
}
느낀점
생략
댓글남기기