[백준] 1331번 나이트 투어 & 2251번 물통

오늘은 2문제이기 때문에 문제는 작성하지 않을 예정..

 

두 문제의 공통점은 bfs 혹은 dfs를 사용한다는 점인 동시에, 완전탐색 문제다.

그러니까 bfs와 dfs가 감미된 완탐(브루트 포스)문제라고 할수 있다.,

 

 

나이트 투어는 기존의 bfs와 dfs와 다르점이 있다면,

스택이나 큐에 넣지 않는점이다. 물론 넣어도 풀 수는 있을 수 도 있다.

하지만... 아무튼 나는 그렇게 풀지 않았다.

먼저 첫번째 값을 검색하고... 그 값을 x좌표랑 y좌표로 나눈다.

 

그리고 저장하고 

2번째 부터도 x좌표랑 y좌표로 나누는데 주의할점은 첫 번째 좌표는 더럽히면 절대 안된다.

더럽히는 순간 끝이다.

왜냐하면 다음 좌표가 무엇인지 확인해야하는데 그렇게 하지 않으면 그럴만한 껀덕지가 없기 때문이다.

여기까지 설명하고... 코드를 보면

package _2020_05_18.B;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {
	
	static int dx[] = new int[]{1,1,2,2,-1,-1,-2,-2};
	static int dy[] = new int[]{2,-2,1,-1,2,-2,1,-1};
	static int isCan[][] = new int[6][6];
	static boolean flag;
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String start = br.readLine();
		
		int x = start.charAt(0) - 'A';
		int y = start.charAt(1) - '1';
		
		isCan[x][y] = 1;
		
		int tx = x;
		int ty = y;
		
		for(int i = 0;i<35;i++) {
			String last = br.readLine();
	
			int lx = last.charAt(0) - 'A';
			int ly = last.charAt(1) - '1';

			flag = false;
			
			for(int k = 0; k<8;k++) {
				int nx = dx[k] + tx;
				int ny = dy[k] + ty;
				
				if (nx < 0 || 6 <= nx || ny < 0 || 6 <= ny) continue;
				
				if (nx == lx && ny == ly && isCan[nx][ny] == 0) {
					isCan[lx][ly] = 1;
					flag = true;
					break;
				}
				
				
			}
		
			if (flag) {
				tx = lx;
				ty = ly;
			} else {
				System.out.println("Invalid");
				return;
			}
			
		}
		
		flag = false;
		for(int i = 0; i<8;i++) {
			
			if ((tx+dx[i]) == x && (ty+dy[i]) == y ) {
				flag = true;
				break;
			}
		}
		
		if (flag) {
			System.out.println("Valid");
		} else {
			System.out.println("Invalid");
		}
	}
}

얼핏 보면.. dfs나 bfs처럼 보이지만... 굳이 dfs나 bfs가 아니여도 좌표를 사용할 수 있다는 것을 배웠다.

따지고 보면 이것도 완탐이 아닐까 생각해본다.

여기서 isCan이라는 부분이 있는데 이 부분은 간단하게 여기 방문했다는 것을 알려주는 그런 장치다.

흔히 boolean으로 이용하는 바로 그거 맞다.

 

그리고 검색하고 바로 빠지는 이유는 

두 가지 이유가 있는데 첫번째는 빠른 진행이고,

두 번째 이유는 이 길은 가능한걸 알려주기 위한 방법이다. 만약 break가 존재하지 않는다면

flag의 값이 계속 바뀌던가 아니면 쓸데 없는 시간을 잡아 먹을 것이다. 하지만 코드상으로는 값이 바뀌는일이 없을 것 같다. 

근데 만약에 false다. 그러면 다음 값을 갈수  없기 때문에 확인할 필요가 없다. 그래서 return을 시켜주면 된다.

아래 flag도 같은 역할이다. 이 두개를 분리 시켜도 무방할듯 싶다.

 

물통은 bfs 또는 dfs로 푸는 문제다. 굳이 bfs로 풀이유는 없다. 하지만 더 효율이 좋다니까 나중에 풀어봐야지..

이 문제는 조금 고민해야되는 문제다.

이번에는 예제를 통해 설명하는게 좋을 것같다.

비커가 A,B,C가 존재한다고 가정하자

그리고 A 는 8 B 는 9 C는 10의 용량이 있다고 하고.. C만  꽉찼다고 한다.

 

그러면 A,B,C가 서로 물을 전달하는 방식은

 

A -> B

A -> C

B -> C

B -> A

C -> A

C -> B

 

내가 이 문제를 풀지 못한 결정적인 이유는 값을 계산할때 이런걸 예상하지 못했다. 나는 무조건 C에서 물을 옮겨야 한다고 생각했다. 하지만 A,B,C모두 자유롭게 물을 옮기는게 가능하였다.

 

주의할점이 있다.

첫 번째는 물을 꽉찰 때까지 물을 주입한다는 거고,

두 번째는 넘치면 안된다는 것이다. 

물론 두 가지 이유는 어떻게 보면 같은 이유다.

 

이제 한 번 해보겠다.

 

먼저 A ->B

A에서 B로 물을 옮긴다고 가정하자.

그러면 A에는 물이 B로 옮겨진다. 그러면 A에는 물은 없어질 것이다. 물론 A에 물이 존재하고 B에도 존재한다면 넘치겠지만... 만약 넘친다면 어떻게 해야할까?

문제에 꽉찰 때까지 물을 옮긴다고 하였으니 A에 남아 있는 물은 

넘기는 물에서 B의 용량을 뺀 값일게 분명하다. 왜냐하면 넘처흘렀다는 이야기는 B의 용량보다 양이 많다는 이야기고.

이 넘친 물은 모두 A에 가 있기 때문이다. 만약 반대라면

A에는 물이 존재하지 않기 때문에 0을 넣어주면 되고, B에는 넘긴 값을 넣어주면 된다.

이때는 꽉차지 않을 수 있기 때문이다.

 

이렇게 위의 모든 것을 계산해주면 된다.

C같은 경우는 넘칠일이 없다고는 하는데 나는 그냥 하였다. 이제 설명하지 않는 부분은 visited만 설명하지 않았다.

package _2020_05_22.C;

import java.io.IOException;
import java.util.Scanner;

public class Main {
	static int A,B,C;
	static boolean visit[][] = new boolean[201][201];
	static boolean ans[] = new boolean[201];
	static void dfs(int ac, int bc, int cc) {
		if (visit[ac][bc]) return;
		
		if (ac == 0) ans[cc] = true;
		
		visit[ac][bc] = true;
		
		// A -> B
		if (ac+bc > B) {
			dfs((ac+bc)-B,B,cc);
		}else {
			dfs(0,ac+bc,cc);	
		}
		
		// A -> C
		if (cc + ac > C) {
		dfs((cc+ac)-C,bc,C);	
		}else { 
		dfs(0,bc,cc+ac);
		}
		
		// B -> A
		if (ac+bc > A) {
			dfs(A,(ac+bc)-A,cc);	
		} else {
			dfs(ac+bc,0,cc);
		}
		
		// C -> A
		if (ac+cc > A) {
			dfs(A,bc,(ac+cc)-A);	
		}else {
			dfs(ac+cc,bc,0);
			
		}
		
		// C -> B
		if (bc+cc > B) {
			dfs(ac,B, (bc+cc)-B);	
		}else {
			dfs(ac,bc+cc, 0);
			
		}
		
		
	}
	public static void main(String[] args) throws NumberFormatException, IOException {
		Scanner sc = new Scanner(System.in);
		
		A = sc.nextInt();
		B = sc.nextInt();
		C = sc.nextInt();
		dfs(0,0,C);
		
		for(int i = 0;i<201;i++) {
			if (ans[i]) {
				System.out.print(i + " ");
			}
		}
		
	}
}
 

아무래도 visited처리를 하는 이유는 이제 같은 방식으로 하지 않겠다는 의지 같다.

dfs이기 때문에 여러 제귀가 등장할 것이고,,, 그것들을 제어 해주지 않으면 대참사가 일어나기 때문이다.

 

 

오늘은 특별하게 2문제를 풀어보았다.

이 문제들은 내 그룹에서 코테 연습삼아 푸는 문제다. 현재는 실버정도까지만 풀고 있지만 골드까지 푸는 것을 목표로 하고 있다.