[크루스칼] 백준 13418번 학교 탐방하기- JAVA

 

 

 

학교 탐방하기 문제...

어려워서 답보고 이해했다ㅠ

 

---

1. 출처

---

 

13418번: 학교 탐방하기

 

 

 

---

2. 설계

---

 

 

오답 설계

처음에는 DFS로 모든 그래프의 갈림길에 대해 검사하고, MIN 값과 MAX 값을 구해주고자 했다.

근데 하나의 위치에 가면 그 위치에서 갈 수 있는 길 중 1개만 선택하게 하는 알고리즘을 짜서

 

이런 경우가 절대 안나왔다. 한 위치에서 모든 갈래를 모두 선택하는 방법이 절대 안나왔던 것이다.

그래서 생각하다가 시간이 오래걸려 그냥 정답을 봤다.

 

 

 

정답 설계

 

[BOJ] 백준 13418번 : 학교 탐방하기 (JAVA)

 

나는 이 분 설계를 참고했다.

 

 

1. 모든 간선을 edgeList에 저장한다.

static List<Edge> edgeList = new ArrayList<>();
.
.
.
for(int i=0;i<M+1;i++){
	String info = br.readLine();
	st = new StringTokenizer(info, " ");
	int A = Integer.parseInt(st.nextToken());
	int B = Integer.parseInt(st.nextToken());
	int updown = Integer.parseInt(st.nextToken()); //0오르막길

	edgeList.add(new Edge(A, B, updown));
}
.
.
.
public static class Edge{
	int start;
	int end;
	int updown;

	public Edge(int start, int end, int updown){
		this.start = start;
		this.end = end;
		this.updown = updown;
	}
}

 

 

 

2. 오르막길 내리막길이냐 기준으로 오름차순 정렬한다.

Collections.sort(edgeList, (e1, e2) -> e1.updown-e2.updown);

 

그럼 오르막길이 0이고, 내리막길이 1이니까 모든 오르막길이 앞에 나와있을 것이다.

 

 

 

3. 오르막길이 가장 많은 길을 전개한다 (크루스칼)

//오르막길이 가장 많은 루트
p = new int[N+1];
order = new int[N+1];
setP();

int count = 0;
        
for(int i=0; i<M+1; i++){
	Edge cur = edgeList.get(i);

	int startP = find(cur.start);
	int endP = find(cur.end);

	if(startP == endP) continue;

	union(cur.start, cur.end);

	if(cur.updown == 0) count++;
            
}

maxR = count*count;


.
.
.

public static void setP(){
	for(int i=0;i<N+1;i++){
		p[i] = i;
	}
}

public static int find(int target){
	if(target == p[target]) return target;
	return p[target] = find(p[target]);
}

public static void union(int a, int b){

	int ap = find(a);
	int bp = find(b);

	if(order[ap]>=order[bp]){
		order[ap]++;
		p[bp] = ap;
	}else{
		order[bp]++;
		p[ap] = bp;
	}
}

 

Collections.sort에 의해서 오르막길이 가장 앞에 정렬되어 있을 것이다.

따라서 edgeList 앞부터 선택해주면서 start와 end 간선의 부모가 같은지 확인한다.

부모가 같으면 다음 간선을 채택하고, 같지 않으면 이번 간선을 채택해 오르막길을 세준다.(count)

 

 

 

4. 내리막길이 가장 많은 길을 전개한다 (크루스칼)

//오르막길이 가장 많은 루트
p = new int[N+1];
order = new int[N+1];
setP();

count = 0;
        
for(int i=M; i>=0; i--){
	Edge cur = edgeList.get(i);

	int startP = find(cur.start);
	int endP = find(cur.end);

	if(startP == endP) continue;

	union(cur.start, cur.end);

	if(cur.updown == 0) count++;
            
}

minR = count*count;


.
.
.

public static void setP(){
	for(int i=0;i<N+1;i++){
		p[i] = i;
	}
}

public static int find(int target){
	if(target == p[target]) return target;
	return p[target] = find(p[target]);
}

public static void union(int a, int b){

	int ap = find(a);
	int bp = find(b);

	if(order[ap]>=order[bp]){
		order[ap]++;
		p[bp] = ap;
	}else{
		order[bp]++;
		p[ap] = bp;
	}
}

 

오르막길 전개와 달라진 것은 for(int i=M; i>=0; i--) for문 부분이랑 minR을 구한다는 것 뿐이다.

 

 

 

5. 결과 도출

System.out.println(maxR-minR);

 

 

---

3. 전체 코드

---

 

import java.io.*;
import java.util.StringTokenizer;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;

class Main {

    static int N;
    static int M;
    static List<Edge> edgeList = new ArrayList<>();
    static int[] p;
    static int[] order;

    static int minR = 987654321;
    static int maxR = 0;
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String NM = br.readLine();
        StringTokenizer st = new StringTokenizer(NM, " ");
        N = Integer.parseInt(st.nextToken());//건물의 수
        M = Integer.parseInt(st.nextToken());//도로의 수

        for(int i=0;i<M+1;i++){
            String info = br.readLine();
            st = new StringTokenizer(info, " ");
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            int updown = Integer.parseInt(st.nextToken()); //0오르막길

            edgeList.add(new Edge(A, B, updown));
        }

        //입력 끝
        
        Collections.sort(edgeList, (e1, e2) -> e1.updown-e2.updown);
        
        //오르막길이 가장 많은 루트
        p = new int[N+1];
        order = new int[N+1];
        setP();

        int count = 0;
        
        for(int i=0; i<M+1; i++){
            Edge cur = edgeList.get(i);

            int startP = find(cur.start);
            int endP = find(cur.end);

            if(startP == endP) continue;

            union(cur.start, cur.end);

            if(cur.updown == 0) count++;
            
        }

        maxR = count*count;


        //내리막길이 가장 많은 루트
        p = new int[N+1];
        order = new int[N+1];
        setP();
        count = 0;
        
        for(int i=M; i>=0; i--){
            Edge cur = edgeList.get(i);

            int startP = find(cur.start);
            int endP = find(cur.end);

            if(startP == endP) continue;

            union(cur.start, cur.end);

            if(cur.updown == 0) count++;
            
        }

        minR = count*count;


        //결과
        System.out.println(maxR-minR);

    }

    public static void setP(){
        for(int i=0;i<N+1;i++){
            p[i] = i;
        }
    }

    public static int find(int target){
        if(target == p[target]) return target;
        return p[target] = find(p[target]);
    }

    public static void union(int a, int b){

        int ap = find(a);
        int bp = find(b);

        if(order[ap]>=order[bp]){
            order[ap]++;
            p[bp] = ap;
        }else{
            order[bp]++;
            p[ap] = bp;
        }
    }

    public static class Edge{
        int start;
        int end;
        int updown;

        public Edge(int start, int end, int updown){
            this.start = start;
            this.end = end;
            this.updown = updown;
        }
    }
}