[백준] 14621번 나만 안되는 연애(Java) - 세무민의 코딩일기

이번 포스팅에서 다룰 문제는 나만 안되는 연애 문제 입니다.

---

1. 문제

---

2. 입출력 및 예시 

---

3. 문제 풀이

이번 문제에서 3가지의 특징을 잘 분석하면 된다.

1. 남초 대학교와 여초 대학들을 연결하는 도로만 이루어져 있다.

-> 이말은 즉 2가지의 정점으로 구분된다는 의미 

2. 사용자들이 다양한 사람과 미팅할 수 있도록 어떤 대학교에서 모든 대학교로 이동 가능하다.

-> 모든 정점들이 모두 이어져서 있어야 한다는 것, 즉 트리형태

3. 시간낭비하지 않고 경로의 최단거리를 구해야 한다.

-> 최소 스패닝 트리

4. 모든 학교를 연결하는 경로가 없을 경우 -1을 출력한다.

-> 학교 정점 == 입력받은 학교의 수 - 1

우선 위의 포인트를 잘 이해하면 문제를 쉽게 접근할 수 있다. 

그래도 이번 문제를 풀기 위해서는 직접 그림을 그려보는 것이 제일 좋은데 제가 풀은 방법을 보여드리면 

위의 그림처럼 그리면서 풀었습니다.

즉 남자 대학교 2개가 겹치면 안되고 여자 대학교 2개가 겹치지 않는 간선들이 생겨야 하는 상황이기 때문에 

u값과 v값에 해당하는 성별 대학교가 성별이 다른지 여부를 체크하여 문제를 접근하면 쉽게 풀 수 있습니다.

성별이 다른 정점과 간선들로 구성된 값들로 최소 스패닝 트리를 구해주면 끝입니다.

---

4. 코드 및 결과

package backjoon_20211003;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

/**
 * [나만 안되는 연애]
 * Q. 남초와 여초 대학을 연결하는 도로만 사심 경로로 연결된다.
 * Q. 어떤 대학에서든 모든 대학교로 이동 가능 
 * Q. 최단거리의 길이를 구하면된다 -> 최소 신장 트리 -> 최소 스패닝 트리
 * Q. 모든학교를 연결하는 경로가 없는 경우 -1을 출력한다.
 * 
 * 
 * 
 * */

class school implements Comparable<school>{

	int fristNode;
	int endNode;
	int result;
	
	school(int fristNode, int endNode, int result){
		this.fristNode = fristNode;
		this.endNode = endNode;
		this.result = result;
	}
	
	@Override
	public int compareTo(school o) {
		return result - o.result;
	}
}


public class backjoon_14621 {

	
	static int[] parent;
	static ArrayList<school> Nodes;
	
	// union-find 선언부
	public static int find(int answer) {
		if(parent[answer] == answer) {
			return answer;
		} else {
			return parent[answer] = find(parent[answer]);
		}
	}
	
	public static void union(int x, int y) {
		x = find(x);
		y = find(y);
		if(y != x) parent[y] = x;
	}
	
	// kruskal
	public static int kruskal(int m) {
		parent = new int[m + 1];
		
		for(int i = 1; i <= m; i++) {
			parent[i] = i;
		}


		Collections.sort(Nodes);
		int result = 0;
		int schoolCount = 0;
		
		for(school node : Nodes) {
			school schoolNode = node;
			
			if(find(schoolNode.fristNode) != find(schoolNode.endNode)) {
				union(schoolNode.fristNode, schoolNode.endNode);
				result += schoolNode.result;
				schoolCount++;
			}
		}
		
		if(schoolCount == m - 1) return result;
		else return -1;
	}
	
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer stringTk;
	
		stringTk = new StringTokenizer(reader.readLine());
		int N = Integer.parseInt(stringTk.nextToken());
		int M = Integer.parseInt(stringTk.nextToken());
		
		String[] sex = new String[N+1];
		Nodes = new ArrayList<school>();
		String checkSex = reader.readLine();
		stringTk = new StringTokenizer(checkSex);
		
		for(int i = 1; i <= N; i++) {
			sex[i] = stringTk.nextToken();
		}
		
		for(int i = 0; i < M; i++) {
			stringTk = new StringTokenizer(reader.readLine());
			int u = Integer.parseInt(stringTk.nextToken());
			int v = Integer.parseInt(stringTk.nextToken());
			int d = Integer.parseInt(stringTk.nextToken());
			
			if(!sex[u].equals(sex[v])) {
				Nodes.add(new school(u, v, d));
			}
		}
		
		int result = kruskal(N);
		
		writer.write(result + "\n");
		writer.flush();
		writer.close();
		reader.close();
		
	}
}

위에서 그림과 설명한 내용을 기반으로 구현했습니다.

기본 Kruskal 로직과 동일하며 해당 로직에서는 마지막에 모든 학교를 연결하는 경로가 있는지 체크만 해주면 됩니다

👉👉 GitHub

GitHub - sg-moomin/programmersStudy

상세한 코드는 GitHub에 동일하게 구성되어 있습니다. 

결과는 성공입니다! 

---

이번 포스팅에서도 최소 스패닝 트리 응용 문제를 풀었는데 아직은 부족한게 많다는 걸 한번더 느꼈습니다.

회사 끝나고 틈틈히 익숙해질 때까지 계속 풀어볼 생각입니다.

다음 포스팅에서는 더 좋은 정보로 찾아오겠습니다.