package Dfs_Bfs;

import java.util.*;

//35min
public class prog_3_단어변환 {
	static int size;
	static String targ;
	static String [] word;
	static int answer = Integer.MAX_VALUE;
	
	public static void dfs(int begin_idx, boolean visited[], int count) {
		String begin = word[begin_idx];
		
		//아니 여기서 == 해줬는데 왜 답 4나와...?
		if(begin.equals(targ)) {
			if(answer>count)
				answer = count;
			return;
		}
		
		//for 돌면서 하나만 다르면 dfs타기
		for(int i=0; i<word.length; i++) {
        	if(visited[i] == true)
        		continue;
        	
			int cnt = 0;
        	for(int j=0; j<size; j++) {
        		if(begin.charAt(j) == word[i].charAt(j))
        			cnt++;
        	}
        	
        	if(cnt == size-1) {
        		visited[i] = true;
        		dfs(i,visited,count+1);//i번째가 새로운 begin이고 visited는 방문한곳은 다시안가게, 1번 바뀌었다는 뜻
        		visited[i] = false;
        	}	
		}
		
	}
	
	
    public static int solution(String begin, String target, String[] words) {
    	//target이 words에 없는 경우
    	boolean b = false;
        for(int i=0; i<words.length; i++) {
        	if(words[i].equals(target))
        		b = true;
        }
        if(b == false)
        	return 0;
        
        size = target.length();
        targ = target;
        word = words;
        //있는 경우
        //size-1개 만큼 같을 경우 dfs 타고 들어간다
        for(int i=0; i<words.length; i++) {
        	int cnt = 0;
        	for(int j=0; j<size; j++) {
        		if(begin.charAt(j) == words[i].charAt(j))
        			cnt++;
        	}

        	if(cnt == size-1) {
        		boolean visited[] = new boolean[words.length];
            	visited[i] = true;
            	
        		dfs(i,visited,1);//i번째가 새로운 begin이고 visited는 방문한곳은 다시안가게, 1번 바뀌었다는 뜻
        	}
        	
        }
        
        return answer;
    }
    
    public static void main(String[] args) {
		String s[] = {"hot", "dot", "dog", "lot", "log", "cog"};
		
		System.out.println("answer "+solution("hit","cog",s));
	}
	
}

package Dfs_Bfs;

import java.util.*;
import java.io.*;

public class beak_소수경로 {

	public static boolean[] prime;
	
	//num부터 숫자 바꿔보기
	//type은 자리수, t는 0~9까지
	public static int changeNum(int num, int type, int t) {
		int result = 0;
		
		switch(type) {
		case 1: //1000의 자리
			result = t*1000;
			result += num - num/1000 * 1000;
			break;
		case 2: //100의 자리
			result = t*100;
			result += (num/1000 * 1000) + (num - num/100 *100);
			break;
		case 3: //10의 자리
			result = t*10;
			result += (num/100*100) + (num- num/10 *10);
			break;
		case 4: //1의 자리
			result = t;
			result += num/10*10;
			break;
		}
		return result;
	}
	
	public static boolean isPrime(int n) {
		if(n == 1)	return false;
		
		for(int i=2; i<n; i++) {
			if(n%i == 0)
				return false;
		}
		return true;
	}
	
	public static void bfs(int start, int end) {
		int count = -1;
		
		boolean visited[] = new boolean[10000];
		
		//int 배열로 초기화한 queue
		Queue<int[]> qu = new LinkedList<int[]>();
		qu.add(new int[] {start,0}); //처음에 큐에 {start,0} 넣음
		
		while(!qu.isEmpty()) {
			//빼기전에 num, cnt에 넣기
			int num = qu.peek()[0];
			int cnt = qu.peek()[1];
			
			qu.poll();//빼고
			if(num == end) {
				if(count == -1 || count > cnt)
					count = cnt;
				continue;
			}
			
			if(num<1000 || visited[num])
				continue;
			
			//이미 방문했던곳이 아니라면
			visited[num] = true;
			
			//순차적으로 1000이 넘으면서 소수인지 확인
			//i는 자리수, j는 0~9까지
			for(int i=1; i<=4; i++) {
				for(int j=0; j<10; j++) {
					int temp = changeNum(num,i,j);
					if(temp>=1000 && prime[temp]) {
						qu.offer(new int[] {temp,cnt+1});
					}
				}
			}
		}//while
		
		if(count == -1)
			System.out.println("Impossible");
		else
			System.out.println(count);
		
	}
	
	public static void main(String[] args) throws IOException{
		Scanner sc = new Scanner(System.in);
		
		int size = sc.nextInt();
		
		prime = new boolean[10000]; //소수인지 아닌지 일단 구하기
		
		//1000부터 10000까지 소수인지 아닌지 찾아서 boolean
		for(int i=1000; i<10000; i++) {
			prime[i] = isPrime(i);
		}
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		for(int i=0; i<size; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			
			bfs(start, end);
		}
	}
}

//참고 블로그 https://pangsblog.tistory.com/31

package Dfs_Bfs;

import java.util.*;

//dfs로 인한 시간초과..ㅎ bfs로 다시
public class beak_빙산 {

	static class Pos{
		int x;
		int y;
		
		Pos(int x, int y){
			this.x = x;
			this.y = y;
		}
	}
	
	
	static int arr[][];
	static int visited[][];
	static int n;
	static int m;
	
	static int dx[] = {0,0,1,-1};
	static int dy[] = {1,-1,0,0};
	
	public static boolean melt() {	
		boolean b = true;
		
		Queue<Pos> qu = new LinkedList<>();
		
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				
				if(arr[i][j] != 0) {
					b = false;
					int chk = 0;
					for(int k=0; k<4; k++) {
						int nx = i + dx[k];
						int ny = j + dy[k];
						
						if(nx>=0 &&nx<n && ny>=0 && ny<m && arr[nx][ny] ==0)
							chk++;
					}
					
					if(arr[i][j] - chk <= 0)
						qu.add(new Pos(i,j));
					else
						arr[i][j] -= chk;
				}
			}
		}
		
		while(!qu.isEmpty()) {
			Pos p = qu.poll();
			arr[p.x][p.y] = 0;
		}
		
		return b;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		m = sc.nextInt();
		
		arr= new int[n][m];
		visited = new int[n][m];

		sc.nextLine();
		
		for(int i=0; i<n; i++) {
			String s = sc.nextLine();
			String sp[] = s.split(" ");
			
			for(int j=0; j<m; j++)
				arr[i][j] = Integer.parseInt(sp[j]);
		}
		
		int answer = 0;
		int year = 1;
		
		while(true) {
			//하나라도 안걸리면 전부 0이라는 소리니까 빠져 나가기
			if(melt())
				break; // 빙산 녹이기

			int size = 0;

			Queue<Pos> qu = new LinkedList<>();
			
			for(int i=0; i<n; i++) {
				for(int j=0; j<m; j++) {
					//visited에는 전년도값, year은 이번년도 값이기때문에, visited가 같거나 크면 continue;
					if(arr[i][j] == 0 || visited[i][j] >= year)
						continue;
					//아니면 빙하가 있는거니까
					size++;
					visited[i][j] = year;
					qu.add(new Pos(i,j));
					
					//qu랑 닿아있는부분 전부 year로 교체
					while(!qu.isEmpty()) {
						Pos p = qu.poll();
						
						for(int k =0; k<4; k++) {
							int nx = p.x +dx[k];
							int ny = p.y +dy[k];
							
							//visited에는 전년도값, year은 이번년도 값이기때문에,전년도가 이번보다 작을때만 들어감
							if(nx>=0 &&nx<n && ny>=0 && ny<m && arr[nx][ny] !=0 && visited[nx][ny] < year){
								visited[nx][ny] = year;
								qu.add(new Pos(nx,ny));
							}
						}
					}//while
				}//in for
			}//out for
			
			
			if(size>=2) {
				answer = year;
				break;
			}
			
			year++;
		}//while
		
		//year가 아니고 answer을 넣어야함
		System.out.println(answer);
	}
}

package Greedy;

import java.util.*;

public class beak_기타줄 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		int m = sc.nextInt();
		
		int set[] = new int[m];
		int one[] = new int[m];
		
		for(int i=0;i<m;i++) {
			set[i] = sc.nextInt();
			one[i] = sc.nextInt();
		}
		
		Arrays.sort(set);
		Arrays.sort(one);

		int min=Integer.MAX_VALUE;
		
		//가장 싼 6팩짜리로만 전부 vs 가장싼 낱개로 전부 구매
		//n/6 후 +1 해주는것 잊지 말기!
		min = Math.min(((n/6)+1) * set[0], one[0] *n);

		//여기서는 몫과 나머지 정확하게 계산해야한다.
		min = Math.min((n/6)*set[0] + (n%6)*one[0], min);
		
		System.out.println(min);
	}
}

	//6팩짜리로만 기타줄을 산다고 가정했을 때는
		(n/6)+1 *set[0] // 로 계산해준다

package Backtracking;

import java.util.*;

//1h
public class beak_NQueen {

	static int n;
	static int answer = 0;
	//cols에는 각 행마다의 "열" 값이 들어있음
	static int cols[]; //cols[level] = x;라면 level이라는 행에 x값은 열; 고로 (level,x) 의미
	
	static public boolean isPossible(int level) {
		//level행에 걸치는지 or i열에 걸치는지
		//대각선에 위치하는지
		//의 조건에만 false
		
		//level전까지의 행의 열값 중 같은것이 존재하는지
		for(int i=0; i<level; i++) {
			//새로 넣고 들어온 level행의 i열 퀸과 전에 존재하던 열에 겹치는게 있다면
			if(cols[level] == cols[i])
				return false;
			//i번째 퀸의 위치와 level 위치의 퀸이 대각선에 존재할 때,
			//level행 - i행 == level열 - i열 이 같으면 대각선!
			if(Math.abs(level-i) == Math.abs(cols[level]- cols[i]))
				return false;
		}
		
		return true;
	}
	
	static public void back_tracking(int level) {
		//level : level-1 까지는 검증 된것이고, level 행을 검증할 차례
		if(level == n) {//0행부터시작해서 n-1까지 만족한거니까 n이라면 그 전을 전부 만족한것
			answer++;
			//만약 각 행의 퀸의 위치(열)를 알고싶다면 cols[i]출력하면 됨
			//for(i<n) sout(cols[i]);
		}
		
		else {
			//level-1까지는 조건대로 만족이고
			//level 행에 (0~n)열까지 퀸 넣어보기
			
			for(int i=0; i<n; i++) {
				cols[level] = i; //level행에 i번째 열에 퀸 넣어보기
				if(isPossible(level)) {
					//퀸을 놔도 되면
					// 다음행으로 넘어가기
					back_tracking(level+1);
				}
			}
		}
	}

	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		
		cols = new int[n];
		boolean visited[][] = new boolean[n][n];
		
		back_tracking(0);
		
		System.out.println("answer " + answer);
	}
}