5회차(01.18) - 결과

<백준>

- Java

---

* 교수님은 기다리지 않는다

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

public class Main {
	static int N,M;
	static int[] diff;
	static int[] parent;
	
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		while(true) {
			st = new StringTokenizer(br.readLine()," ");	
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			
			if(N==0 && M==0) break;
			
			diff= new int[N+1]; //차이
			parent = new int[N+1]; //무게 잰거 저장
			
			for(int i =0; i<=N; i++) {
				parent[i]=i;
			}
			
			String q;
			int a,b,w;
			
			for(int i=1; i<=M; i++) {
				st = new StringTokenizer(br.readLine()," ");
				q = st.nextToken();
				a = Integer.parseInt(st.nextToken());
				b = Integer.parseInt(st.nextToken());
				if(q.equals("!")) { //상근이가 무게 잼
					w = Integer.parseInt(st.nextToken());
					union(a,b,w);
				}else if(q.equals("?")) { //교수님이 물어보심
					if(find(a)==find(b)) { // 두 샘플 무게 쟀었는지 확인
						bw.write(diff[b]-diff[a]+"\n");
					}else { // 두 샘플 무게 잰적 없으면 차이 구 할 수 없으므로!
						bw.write("UNKNOWN"+"\n");
					}
				}
			}	
		}
		bw.flush();
		bw.close();	
	}
	
	static void union(int a, int b, int w) {
		int parentA = find(a);
		int parentB = find(b);
		//무게차이 갱신
		diff[parentB]=diff[a]-diff[b]+w;
		parent[parentB]=parentA;
	}
	
	static int find(int n) { //부모 갱신하며 n 찾음
		if(parent[n]==n) return n;
		
		int parentIndex = find(parent[n]);
		diff[n]+=diff[parent[n]];
		return parent[n]=parentIndex;
	}
}

 

union - find 문제

 

q(query)에 따라 union과 find를 실행해준다.

 

이때 diff 배열엔 무게 차이를 저장하고, parent 배열엔 부모를 저장한다.

 

q가 ! 이면 상근이가 무게를 재는 경우이므로,

union을 실행하여 무게차이를 갱신해주며 parent 설정해준다.

 

q가 ? 이면 교수가 무게 차이를 묻는 것이기 때문에 

find를 수행해 부모를 갱신하며 찾는다.

find를 통해 찾지못하면 재지 못한 경우로 무게를 차이를 구할 수 없어 unknown을 출력한다.