각종 알고리즘 모듬탕 Part 2

역시나 분류 따윈...

package com.kei;

import java.util.PriorityQueue;

public class DFS_wordConvert {

	
	static PriorityQueue<Integer> _pq;
	static String[] _words;	
	static String _target;
	static boolean _first;	
	
	static void dfs(String nWord, int idx, int count, boolean[] visited, String log) {
		
		// hit 로 첨에 들어 오는건 처리하지 않는다.
		if(_first == false) {	
			count++;
			visited[idx] = true;
		} 		
		_first = false;
		
		if(nWord.equals(_target)){
			System.out.println(log + " >> " + count);
			_pq.offer(count);
			return;
		}
		
		for(int i = 0 ; i < _words.length ; i++) {
			String getStr = _words[i];
			if (visited[i] == false) {						
				int match = 0;
				for(int c1 = 0 ; c1 < nWord.length() ; c1++) {
					char ca1 = nWord.charAt(c1);					
					char ca2 = getStr.charAt(c1);
					if ( ca1 == ca2 ) {
						match++;					
					}
				}
				
				if(match >= getStr.length() - 1) {					
					// ★★★★★★★★★★★★ 요주의 ★★★★★★★★★★★★★★★ 
					// 배열을 저렇게 보내면 주소를 들고 가기 때문에, 같은 값을 보게 되는 문제가 발생한다.
					// 배열을 새로 만들어서 날려야, 별도로 처리 된다.
					boolean[] sendVisit = new boolean[_words.length];
					for(int x = 0 ; x < _words.length ;  x++) {
						sendVisit[x] = visited[x];
					}
					
					dfs(_words[i], i, count, sendVisit, log + " " + _words[i]);					
				}
			}
		}
		
		
	}
	
	public static void main(String[] args) {
		String begin = "hit";
		String target = "cog";
		//String[] words = {"hot", "dot", "dog", "lot", "log", "cog"};
		String[] words = {"cog", "log", "lot", "dog", "dot", "hot"};
		int answer = 0;
		
		_words = words;
		_target = target; 
		_pq = new PriorityQueue<Integer>();	// 기본 오름차순 정렬
		boolean[] visited = new boolean[words.length];
					
		_first = true; 
		dfs(begin, 0, 0, visited, "");		
		
		System.out.println(_pq);
		if(_pq.isEmpty() == false) {
			answer = _pq.peek();
		}
		System.out.println("answer : " + answer);
				
	}

}

package com.kei;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.PriorityQueue;

import com.kei.Dijkstra.Node;

public class Dijkstra2 {

	public static void main(String[] args) {
		int departure = 1;
		int arrival = 8;
		int nodeCnt = 6;
		int[][] paths = {{1,2,3}
		                ,{1,3,8}
		                ,{1,4,5}
		                ,{2,3,2}
		                ,{2,4,3}
		                ,{2,5,5}
		                ,{2,6,5}
		                ,{3,5,1}
		                ,{4,6,5}
		                //,{4,6,1}
		                ,{5,6,1}};
		
		ArrayList<ArrayList<Node>> pathArr = new ArrayList<ArrayList<Node>>();
		
		for(int i = 0 ; i <= nodeCnt ; i++) {
			pathArr.add(new ArrayList<Node>());
		}
		
		for(int i = 0 ; i < paths.length ; i++) {
			int s = paths[i][0];
			int e = paths[i][1];
			int d = paths[i][2];
			
			pathArr.get(s).add(new Node(e, d));
		}
		
		int[] distArr = new int[nodeCnt+1];
		Arrays.fill(distArr, Integer.MAX_VALUE);
		
		PriorityQueue<Node> pq = new PriorityQueue<Node>();
		pq.add(new Node(departure, 0));
		distArr[departure] = 0;
		
		while(pq.isEmpty() == false) {
			Node cur = pq.poll();
			int now = cur.idx;
			int dist = cur.dist;
			if (distArr[now] < dist) continue;
			
			for(int i = 0 ; i < pathArr.get(now).size() ; i++) {
				Node getNd = pathArr.get(now).get(i);
				int cost = distArr[now] + getNd.dist;
				if(cost < distArr[getNd.idx]) {
					distArr[getNd.idx] = cost;
					pq.offer(new Node(getNd.idx, cost));
				}
			}
			
			Iterator<Node> itr = pq.iterator();
			while(itr.hasNext()) {
				Node pn = itr.next();
				System.out.print(pn.idx + "(" + pn.dist + "), ");
			}
			System.out.println();
			System.out.println(Arrays.toString(distArr));
		}
		
	}
	
	static class Node implements Comparable<Node> {
		int idx;
		int dist;
		
		Node(int i, int d){
			this.idx = i;
			this.dist = d;
		}
		
		// comparator 의 compare 는 처음 넣을 때 큐가 비어 있을 대 오류가 발생한다.
		// comparable 의 compareTo는 상관 없더라.
		public int compareTo(Node o) {
			return this.dist - o.dist;	// 오름차순
		}		
	}

}

package com.kei;

import java.util.HashSet;
import java.util.Iterator;

public class DP_NPresent {
	// N이 주어 질 때 N으로 사칙연산을 수행해서 몇개의 N 으로 타겟 숫자를 만들 수 있는지. N의 갯수를 출력하라.
	static HashSet<Integer>[] dp = new HashSet[9];
	
	public static int solution(int N, int number) {	      
       if(N==number) {
			return 1;
		}       
		String n_ = String.valueOf(N);		
		for(int i=0;i<=8;i++) {
			dp[i] = new HashSet<Integer>();
			if(i==1) dp[1].add(Integer.parseInt(n_));
			if(i<2 ) continue;
            //ex ) dp[3]에 NNN이 들어갈 수 있도록 지정
			n_+=String.valueOf(N);
			dp[i].add(Integer.parseInt(n_));
			for(int j=1;j<i;j++) {
				 calc(j,i);
                 //찾으려는 number가 만들어졌을 경우 바로 리턴
				 if(dp[i].contains(number)) {
					 return i;					 
				 }	
			}
		}
		return -1;
	}	
	
    //각각 N의 개수마다 사칙연산을 해서 배열에 담아줌
	static void calc(int a,int b) {

		Iterator<Integer> listA = dp[a].iterator();
		Iterator<Integer> listB = dp[b-a].iterator();
		
		while(listA.hasNext()) {
			int numA = listA.next();

			while(listB.hasNext()) {
				int numB = listB.next();
				dp[b].add(numA+numB);
				dp[b].add(numA-numB);
				dp[b].add(numA*numB);
				if(numB!=0)
				dp[b].add(numA/numB);			
			}
			listB = dp[b-a].iterator();
		}
	}
	
	public static void main(String[] args) {
		int N = 4;	// 1 ~ 9
		int number = 17;	// 1 ~ 32000
		int answer = -1;
		// 나누기 나머지 무시
		// MIN > 8 return - 1
		
		answer = solution(N, number);
		
		System.out.println(answer);
	}
}

package com.kei;

public class fibonacci {

	public static void main(String[] args) {		
		// 1 1 2 3 5 8 13 21 34

		int target = 8;		
		int[] piboArr = new int[2];		
		for(int i = 1 ;  i <= target ; i++) {
			if(i < 2) {
				piboArr[piboArr.length - i] = i;
				System.out.print(piboArr[piboArr.length - i] + " ");
				continue;
			}
			int sum = piboArr[0] + piboArr[1];
			piboArr[0] = piboArr[1];
			piboArr[1] = sum;
			System.out.print(piboArr[1] + " ");
		}
		
		System.out.println();
		
		for(int i = 1 ; i <= target ; i++) {
			System.out.print(fibo(i) + " ");
		}
	}
	
	static int fibo(int get) {
		if(get < 2) return get;
		return fibo(get - 2) + fibo(get - 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);
	}

}