각종 알고리즘 모듬탕 Part 1

분류 따윈 아직 없다.

package com.kei;

import java.util.Arrays;
import java.util.PriorityQueue;

public class Kruscal {

	static class Node implements Comparable<Node>{
		int st;
		int ed;
		int di;
		
		public Node(int s, int e, int d) {
			this.st = s;
			this.ed = e;
			this.di = d;
		}
		
		// 짧은 거리순으로 큐에 넣는다.
		public int compareTo(Node n) {
			return this.di - n.di;
		}
	}
	
	static int[] parent;
	
	// 최상위 부모를 찾아서 바꿔치기 한다.
	// [1] = 2 -> [2] = 3 -> [3] = 3 -> [2] = 3 -> [1] = 3
	static int find(int a) {
		if(a == parent[a]) return a;
		parent[a] = find(parent[a]);
		return parent[a];
	}
	
	// 부모를 한쪽으로 몰아 넣는다.
	// [1] = 1 -> [2] = 2
	// [1] = 2
	// [2] = 2
	static void union(int a, int b) {
		int aRoot = find(a);
		int bRoot = find(b);
		
		if(aRoot != bRoot) {	// 양쪽리스트의 부모가 동일하지 않으면, 한쪽으로 몰아 넣는다. 
			parent[aRoot] = b;
		} else {
			return;
		}
	}	
	
	static PriorityQueue<Node> pq;
	public static void main(String[] args) {

		int N = 5;
		int[][] input = {{1,3,32}, {1,2,8}, {2,3,2}, {2,4,4}, {3,4,16}, {4,5,1}};
		parent = new int[N + 1];
		
		pq = new PriorityQueue<Node>();
		
		for(int i = 0 ; i < input.length ; i++) {
			pq.add(new Node(input[i][0], input[i][1], input[i][2]));
		}
		
		// 최초는 자기 자신이 부모
		for(int i = 0 ; i <= N ; i++) {
			parent[i] = i;
		}
		
		//System.out.println(Arrays.toString(parent));
		
		int answer = 0;
		
		// 거리가 짧은 것 부터 오름차순으로 순서대로 처리 한다.
		for(int i = 0 ; i < input.length ; i++) {
			Node nd = pq.poll();
			int start = nd.st;
			int end   = nd.ed;
			int dist  = nd.di;
			
			int a = find(start);
			int b = find(end);
			System.out.println(start + " " + end + " " + Arrays.toString(parent));
			
			// 부모 노드가 동일하면 이미 최소 거리이므로 거리를 계산하지 않고 넘어 간다.
			if(a == b) continue;
			
			// 부모를 한쪽 노드로 몰아 넣는다.
			union(start, end);
			answer = answer + dist;	// 전체 노드 탐색 최소비용
			
			System.out.println(">> " + Arrays.toString(parent));
		}		
		
		System.out.println(answer);
	}

}

 

package com.kei;

import java.util.Arrays;

public class DFS_Network {
	
	static boolean visited[];
	static int[][] _computers;
	static int _n;
	
	static void dfs(int m) {
		visited[m] = true;
		System.out.println(m + " "+ Arrays.toString(visited));
		//System.out.println("dfs > " + m);
		for(int i = 0 ; i < _n ; i++) {
			if ( _computers[m][i] == 1 && visited[i] == false) {
				System.out.println("call " + m + ", " + i);
				dfs(i);
			}
		}
	}
	
	public static void main(String[] args) {
		int[][] computers = {{1,1,0},{1,1,0},{0,0,1}};
		int n = 3;
		int answer = 0;
		_computers = computers;
		_n = n;
		visited = new boolean[n];
		for(int i  = 0 ; i < n ; i++) {
			System.out.println(i + " >>>> "+ Arrays.toString(visited));
			if (visited[i] == false) {
				answer++;
				dfs(i);
			}
		}		
		System.out.println(answer);
	}	
	
}

package com.kei;

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

public class DFS_PATH_RoadsAndLibaries2 {

	static List<List<Integer>> adj;
	static boolean[] visited;
	static int count;
	public static void main(String[] args) {
		
		
//		int[][] paths = {{1,3},{3,4},{2,4},{1,2},{2,3},{5,6}};
//		int c_lib = 2;
//		int c_road = 5;
		
		int[][] paths = {{1,2},{3,1},{2,3}};
		int c_lib = 2;
		int c_road = 1;
		int n = 3;
		
		adj = new ArrayList<>();
		for(int i = 0 ; i < n ; i++) {
			adj.add(new ArrayList<>());			
		}
		
		visited = new boolean[n];
		
		for(int i = 0 ; i < paths.length ; i++) {
			int c1 = paths[i][0];
			int c2 = paths[i][1];
			
			adj.get(c1 - 1).add(c2 - 1);
			adj.get(c2 - 1).add(c1 - 1);
		}
		
		System.out.println(adj);
		
		
		
		count = 0;
		int roadCnt = 0;
		int totRoadCost = 0; 
		for(int i = 0 ; i < adj.size() ; i++) {
			if(visited[i] == false) {
				System.out.println("@@ " +  i);
				count++;
				roadCnt = dfs(i, roadCnt);
			}
			
			System.out.println("----------- " + roadCnt);
			totRoadCost = totRoadCost + roadCnt;
			roadCnt = 0;
		}		
		
		totRoadCost = totRoadCost - count;	// 그룹별로 도로 한개씩을 빼줘야 한다.
		System.out.println("1# groups : " + count + " , totRoad : " + totRoadCost);
		System.out.println("2# " + ((count * c_lib) + (totRoadCost * c_road)));
		System.out.println("3# " + (c_lib * n));
		
//		1# 2 4
//		2# 24
//		3# 12

	}
	
	static int dfs(int i, int roadCnt) {
		int totCost = 0;
		roadCnt++;
		System.out.println(">> " + (i + 1));
		visited[i] = true;
		
		List<Integer> list = adj.get(i);
		for(int z = 0 ; z < list.size() ; z++) {
			if(visited[list.get(z)] == false) {
				roadCnt = dfs(list.get(z), roadCnt);
			}
		}		
		
		return roadCnt;
	}

}

package com.kei;

public class DFS_TargetNumber {

    static int _target;
	static int[] _numbers;
	static int _answer = 0; 
	public static void main(String[] args) {
		int[] numbers = {1,1,1,1,1};
        _target = 3;
        _numbers = numbers;
        
		dfs(0, 0);
		int answer = _answer; 
		System.out.println(answer);
	}
	
    public static void dfs(int idx, int sum) {
		
		if(idx == _numbers.length) {
			if (sum == _target) {
				_answer++;
			}
			return;
		}
		
		int get = _numbers[idx];
		idx++;
		dfs(idx, sum + get);
		dfs(idx, sum - get);
	}

}