[알고리즘] 5일차_그래프

 

 

 

P1717 집합의 표현

 

/*P1717 집합의 표현*/
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	static int N,M;
	static int[] parent;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		parent = new int[N+1];
		
		for (int i = 0; i <=N; i++) {
			parent[i] = i;
		}
        int operation;
		int a,b;
        
		for (int m = 0; m < M; m++) {
			st = new StringTokenizer(br.readLine());
			operation = Integer.parseInt(st.nextToken());
			a = Integer.parseInt(st.nextToken());
			b = Integer.parseInt(st.nextToken());
			
			if(operation == 0) {
				//union
				union(a,b);
			} else if(operation == 1) {
				//find
				bw.write(find(a) == find(b) ? "YES\n":"NO\n");
			} else {
				//non-case
				
			}
		}
		
		bw.close();
		br.close();
		
		}
	
	
	static void union(int a,int b) {
		int x = find(parent[a]);
		int y = find(parent[b]);
		
		if(x<y) parent[y] = x;
		else if (x>y) parent[x] = y;
	};
	
	static int find(int a) {
		if(parent[a] == a) return a;
		return parent[a] = find(parent[a]);
	}
	
	

}

 

 

서로소집합 _ union, find

https://born2bedeveloper.tistory.com/29

[JAVA] 서로소 집합(Disjoint Sets)과 연산(Union & Find)

 

 

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

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int N,M;
	static int[] parent;
	static int[] ws;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		while(true) {
			st = new StringTokenizer(br.readLine());	
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			
			if(N == 0) {
                break;
            }			
			parent = new int[N+1];
			ws = new int[N+1];
			
			for (int i = 1; i <=N ; i++) {
				parent[i] = i;
			}
			
			for (int i = 0; i < M; i++) {
				st = new StringTokenizer(br.readLine());
				String cmd = st.nextToken();
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				
				if(cmd.equals("!")) {
					int w = Integer.parseInt(st.nextToken());
					union(a,b,w);
				}else {
					if(find(a) != find(b)) {
						sb.append("UNKNOWN" + "\n");
					}else {
						sb.append(ws[b] - ws[a] + "\n");
					}
				}
				
			}
			
		}
		System.out.println(sb.toString());
		
		
		}
	
	
	static void union(int a,int b, int w) {
		int x = find(a);
		int y = find(b);
		
		if (x > y) {
			int temp = ws[b] - w;
			ws[x] = temp - ws[a];
			parent[x] = y;
		}else {
			int temp = ws[a] + w;
			ws[y] = temp - ws[b];
			parent[y] = x;
		}
	}
	
	static int find(int a) {
		if(parent[a] == a) return a;
		
		int parentId = find(parent[a]);
		ws[a] += ws[parent[a]];
		return parent[a] = parentId;
	}
	
	

}

 

 

P2252. 줄 세우기

package day05.P2252;
/*  백준 2252.줄 세우기  */
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.Writer;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	static int N,M;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		int indegree[] = new int[N+1]; // 간선리스트 생성
		ArrayList<Integer> adj[] = new ArrayList[N+1];
			
		for (int i = 1; i <= N; i++) {
			adj[i] = new ArrayList<>(); // 간선리스트 초기화
		}
		
		int s,e;
		for (int i = 0; i <  M; i++) {
			st = new StringTokenizer(br.readLine());
			s = Integer.parseInt(st.nextToken());
			e = Integer.parseInt(st.nextToken());
			
			adj[s].add(e); //s에서 e로가는 간선 추가
			indegree[e]++; // 진입차수? 증가시킴
			
		} // indegree 배열 완성
		
		Queue<Integer> q = new ArrayDeque();
		
		for (int i = 1; i <= N; i++) {
			if(indegree[i] == 0) {
				q.offer(i); // 진입차수가 0인 노드부터 큐에 넣음
				System.out.print(i + " ");
			}
		}
			
		while(!q.isEmpty()) {
			int zeroNode = q.poll();  //큐에서 하나 꺼냄
			for(int node : adj[zeroNode]) {
				indegree[node]--; // 간선 끊는 거 생각해서 걔네들의 indegree 하나 줄임
				if(indegree[node] == 0) {
					q.add(node);
					System.out.print(node + " ");
				}
			}
		}
		
		
		
		}	

}

 

P1922 . 네트워크 연결

 

 

왜 런타임 오류 나지...???

package day05.P1922;
/*  백준 1922. 네트워크 연결  */
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.Writer;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Queue;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
	
	static int N,M;
	static int[] parent;
	static int[][] graph;
	static int cost;
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(new InputStreamReader(System.in));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken());
		
		graph = new int[M][3];
		parent = new int[N+1];
		for (int i = 0; i <  M; i++) {
			
			graph[i][0] = sc.nextInt();
			graph[i][1] = sc.nextInt();
			graph[i][2] = sc.nextInt();
		} 
		
		for (int i = 1; i <= N; i++) {
			parent[i] = i;
		}
		Arrays.sort(graph, Comparator.comparingInt((int[] o) -> o[2]));
		
		
		long ans = 0;
		for (int i = 0; i < M; i++) {
			if(find(graph[i][0]) != find(graph[i][1])){
				union(graph[i][0], graph[i][1]);
				ans += graph[i][2];
			}
		}
		System.out.println(ans);
		
		
		
		}
	
	static void union(int a,int b) {
		int x = find(parent[a]);
		int y = find(parent[b]);
		
		if(x<y) parent[y] = x;
		else if (x>y) parent[x] = y;
	};
	
	static int find(int a) {
		if(parent[a] == a) return a;
		return parent[a] = find(parent[a]);
	}

}

 

 

 

프림 알고리즘 설명

 

package day05.prim;

import java.awt.List;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	static class Edge implements Comparable<Edge>{
		int e;
		int c;
		public Edge(int e, int c) {
			this.e = e;
			this.c = c;
		}
		@Override
		public int compareTo(Edge o) {
			return this.c - o.c;
		}
	}
	
	
	static int N,M;
	static List<Edge>[] adj;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		M = Integer.parseInt(br.readLine());
		
		adj = new ArrayList[N+1];
		
		for (int i = 0; i <= N; i++) {
			adj[i] = new ArrayList();
		}
		
		int s,e,c;
		Edge edge;
		for (int i = 0; i < M; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine()); 
			s = Integer.parseInt(st.nextToken());
			e = Integer.parseInt(st.nextToken());
			c = Integer.parseInt(st.nextToken());
			adj[s].add(new Edge(e,c)); //간선리스트 (양방향으로 만듦)
			adj[e].add(new Edge(s,c));
		}
		
		long ans = 0;
		boolean[] visit = new boolean[N+1];
		
		PriorityQueue<Edge> pq = new PriorityQueue();
		pq.offer(new Edge(1,0));
		
		Edge now;
		while(!pq.isEmpty()) {
			now = pq.poll();
		
			if(visit[now.e]) continue;
			
			visit[now.e] = true;
			ans += now.c;
			
			for(Edge next : adj[now.e]) {
				if(!visit[next.e]) {
					pq.add(next);
				}
			}
		}
		System.out.println(ans);
	}

}