구르는 돌에는 이끼가 끼지 않는다

https://programmers.co.kr/learn/courses/30/lessons/43162

package com.ji.study;

public class Network {
	
	public static void main(String[] args) {
		int n = 3;
		int[][] com = {{1,1,0},{1,1,1},{0,1,1}};
		System.out.println(solution(n, com));
	}

	public static int solution(int n, int[][] computers) {
		int answer = 0;
		
		// computers.length => 3
		boolean[] visited = new boolean[computers.length];
		
		for(int i=0; i<computers.length; i++) {
				if(visited[i] == false) {
					answer++;
					dfs(i,visited,computers);
				}
				
		}
		
		return answer;
	}
	
	static void dfs(int node, boolean[] visited, int[][] computers) {
		visited[node] = true;
		
		for(int i=0; i< computers.length; i++) {
			if(visited[i] == false && computers[node][i] == 1)
				dfs(i, visited, computers);
		}
	}

}

https://programmers.co.kr/learn/courses/30/lessons/42862

package com.ji.greedy;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class GymSuit {

	public static void main(String[] args) {
		System.out.println(solution(5, new int[] { 2, 4 }, new int[] { 1, 3, 5 }));
		System.out.println(solution(5, new int[] { 2, 4 }, new int[] { 3 }));
		System.out.println(solution(3, new int[] { 3 }, new int[] { 1 }));
		System.out.println(solution(3, new int[] { 1, 2 }, new int[] { 2,3 }));
	}

	public static int solution(int n, int[] lost, int[] reserve) {
		int answer = 0;

		Arrays.sort(lost);
		Arrays.sort(reserve);

		List<PersonVO> sendPossibleList = new ArrayList<PersonVO>();
		for (int i = 1; i <= n; i++) {

			PersonVO personVO = new PersonVO();
			personVO.setIndex(i);
			personVO.setTotal(1);

			if (Arrays.binarySearch(lost, i) >= 0)
				personVO.setTotal(personVO.getTotal() - 1);

			if (Arrays.binarySearch(reserve, i) >= 0)
				personVO.setTotal(personVO.getTotal() + 1);
			
			sendPossibleList.add(personVO);
		}

		for (int i = 1; i < sendPossibleList.size(); i++) {

			if (sendPossibleList.get(i).getTotal() > 1 && sendPossibleList.get(i - 1).getTotal() == 0) {
				sendPossibleList.get(i - 1).setTotal(1);
				continue;
			}
			
			if(i+1 >= sendPossibleList.size())
				continue;
			
			if (sendPossibleList.get(i).getTotal() > 1 && sendPossibleList.get(i + 1).getTotal() == 0) {
				sendPossibleList.get(i + 1).setTotal(1);
				continue;
			}

		}

		for (PersonVO vo : sendPossibleList) {
			if (vo.getTotal() > 0)
				answer++;
		}

		return answer;
	}

}

class PersonVO {
	Integer index;
	Integer total;

	public Integer getIndex() {
		return index;
	}

	public void setIndex(Integer index) {
		this.index = index;
	}

	public Integer getTotal() {
		return total;
	}

	public void setTotal(Integer total) {
		this.total = total;
	}

}

https://www.acmicpc.net/problem/1197

package com.ji.beakjoon.tree;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

/**
 * 최소 신장 트리
 * Kruskal Algo
 * 1. 가중치가 가장 작은 간선을 찾아서 선택
 * 2. 가중치가 작은 간선이 값이 동일할 경우 노드의 번호가 빠른거 선택
 * 3. 순환이 생길 경우는 건너뜀
 * @author ji
 *
 */
public class MST {

	static int n, m;
	static int[] parent;
	static PriorityQueue<edge> pq = new PriorityQueue<edge>();
	static int result = 0;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		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 + 1; i++) {
			parent[i] = i;
		}

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			//A정점, B정점, 간선 가중치
			pq.add(new edge(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken())));
		}

		// 시작점과 종료점의 최상위 노드를 찾아서 겹치면 사이클이 생기는 것이므로 continue를 한다.
		// 아니면 union을 통해 연결하고 v(가중치) 를 더해준다.
		for (int i = 0; i < m; i++) {
			edge tmp = pq.poll();

			int a = find(tmp.s);
			int b = find(tmp.e);

			//순환이 생기므로 패스
			if (a == b)
				continue;
			union(a, b);
			result += tmp.v;
		}

		System.out.println(result);

	}

	// 이 부분이 이해가 확실히 가지 않음 !!!
	// 크루스칼의 기본 union find!! 외워두는게 편하다.
	public static int find(int a) {
		if (a == parent[a])
			return a;
		parent[a] = find(parent[a]);
		return parent[a];
	}

	public static void union(int a, int b) {
		int aRoot = find(a);
		int bRoot = find(b);

		if (aRoot != bRoot) {
			parent[aRoot] = b;
		} else {
			return;
		}
	}
}

//간선 class
//우선순위 큐를 사용하기 위해서 Comparable을 통해 정렬 우선순위를 정했다. (V 기준)
//가중치가 작은 간선을 선택!!!
class edge implements Comparable<edge> {
	int s;
	int e;
	int v;

	public edge(int s, int e, int v) {
		this.s = s;
		this.e = e;
		this.v = v;
	}

	@Override
	public int compareTo(edge arg0) {
		// TODO Auto-generated method stub
		return arg0.v >= this.v ? -1 : 1;
	}

}