[PS] 백준 12851/숨바꼭질 2 - 자바 풀이

숨바꼭질2

 

문제

 

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고, 가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

둘째 줄에는 가장 빠른 시간으로 수빈이가 동생을 찾는 방법의 수를 출력한다.

 

잘못된 코드 및 리뷰

 

숨바꼭질 문제에 각 점에 도달하는 경우의 수를 추가한 문제이다. 얼핏 봤을 때는 단번에 코드를 작성했다. 그런데 틀렸다. 내가 우선 작성한 에러 코드는 아래와 같다.

 

import java.util.*;
import java.math.*;

class Main{
	public static int MAX = 100000;
	public static boolean checked[] = new boolean[MAX+1];
	public static int min = Integer.MAX_VALUE;
	public static int methodCnt = 0;
	
	public static void main(String args[]){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		
		bfs(n, k);
		
		System.out.println(min);
		System.out.println(methodCnt);

	}
	
	public static void bfs(int n, int k) {
		Queue<Position> q = new LinkedList<>();
		q.add(new Position(n, 0));
		while(!q.isEmpty()) {
			Position now = q.poll();
			
			//System.out.println(now.x);
			if(now.x == k) {
				if(now.cnt < min) {
					methodCnt = 0;
					min = now.cnt;
				}
				if(now.cnt == min) {
					methodCnt++;
				}
				continue;
			}
			//분기 한정2
			if(now.cnt + 1 <= min) {
				if(now.x-1 >= 0 && !checked[now.x-1]) {
					q.add(new Position(now.x-1, now.cnt+1));
					if(now.x-1 != k) checked[now.x-1] = true;
				}
				if(now.x+1 <= MAX && !checked[now.x+1]) {
					q.add(new Position(now.x+1, now.cnt+1));
					if(now.x+1 != k) checked[now.x+1] = true;
				}
				if(now.x*2 <= MAX && !checked[now.x*2]) {
					q.add(new Position(now.x*2, now.cnt+1));
					if(now.x*2 != k) checked[now.x*2] = true;
				}
			}
		}
	}
}

class Position{
	int x;
	int cnt;
	Position(int x, int cnt){
		this.x = x;
		this.cnt = cnt;
	}
}

 

갈 수 있는 각 경우를 BFS로 돌며 삽입하고 있다. 그리고 바로 방문 처리를 하여 메모리 낭비를 줄였다. 그런데 정답이 아니다. 반례는 0에서 3으로 가는 경우가 있었다.

 

0 → 1(1증가) →2(1증가) →3(1증가)

0 → 1(1증가) →2(2를 곱함) →3 (1증가)

 

위 경우 모두 정답에 포함되어야 하지만, 나의 경우 2를 방문했을 떄 checked를 true로 해버려 다음 *2로 2가 되는 경우를 막아버린 것이었다.

 

DFS가 아니라 BFS를 쓴 이유?

문제는 방문의 최소 비용을 찾는 것이다. 만약 DFS로 접근 할 경우, 비용을 더해가며 한 노드를 끝까지 파고들텐데, 그럴 경우 종료 조건을 적용하면 방문 배열(여기서는 checeked)에 의존하게 된다. 즉, 방문 가능한 모든 경우를 방문 하고 나서야 그 노드의 역할이 끝날 것이다. 즉 많은 비용을 소모하게 된다.

 

반면 BFS로 할 경우 현재 노드에서 갈 수 있는 모든 경우의 수를 한 번에 순차적으로 훑게 된다. 그 와중에 정답이 나왔을 경우, 그것을 우선 임시 정답(min)으로 설정 한 후, 다른 노드들의 비용이 min보다 클 경우 정답 후보에서 탈락되므로 더 이상 확인할 필요가 없어진다. 

 

즉 BFS를 사용할 경우 처음 min을 찾는 데까지 시간이 절약되고, 분기 한정법을 이용하여 조건에 부합하지 않을 것들을 미리 탈락시켜 비용을 줄일 수 있다.

 

이후 정답을 도출하려 아래 시도를 해보았다.

import java.util.*;
import java.math.*;

class Main{
	public static int MAX = 100000;
	public static boolean checked[] = new boolean[MAX+1];
	public static int min = Integer.MAX_VALUE;
	public static int methodCnt = 0;
	
	public static void main(String args[]){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		
		bfs(n, k);
		
		System.out.println(min);
		System.out.println(methodCnt);

	}
	
	public static void bfs(int n, int k) {
		Queue<Position> q = new LinkedList<>();
		q.add(new Position(n, 0));
		while(!q.isEmpty()) {
			Position now = q.poll();
			
			//System.out.println(now.x);
			
			//종료 조건
			if(now.x == k) {
				if(now.cnt < min) {
					methodCnt = 0;
					min = now.cnt;
				}
				if(now.cnt == min) {
					methodCnt++;
				}
				continue;
			}
			//분기 한정 1
			if(Math.abs(n - k) < Math.abs(now.x - k)) continue;
			
			//분기 한정2
			if(now.cnt + 1 <= min) {
				if(now.x-1 >= 0) {
					q.add(new Position(now.x-1, now.cnt+1));
				}
				if(now.x+1 <= MAX) {
					q.add(new Position(now.x+1, now.cnt+1));
				}
				if(now.x*2 <= MAX) {
					q.add(new Position(now.x*2, now.cnt+1));
				}
			}
		}
	}
}
//0 3에서
//0->1->2->3(1증가, 2곱하기, 1더하기)
//0>1->2->3(1증가, 2증가, 3증
class Position{
	int x;
	int cnt;
	Position(int x, int cnt){
		this.x = x;
		this.cnt = cnt;
	}
}

 

즉 조건을 더욱 빡빡하게 한 것이다.

if(Math.abs(n - k) < Math.abs(now.x - k)) continue;

위 조건은 단순 거리값이 더 클 경우 현재 노드는 결코 최소 비용일 수 없으니 포기하라는 의미이다.(0에서 5로 갈때 적어도 +1만 해도 5의 비용으로 갈 수 있으므로)

 

if(now.cnt + 1 <= min) 

위 조건은 다음 cnt가 min보다 작거나 같을 경우에만 정답의 후보가 된다는 것이다.

 

그럼에도 역시 노드의 방문 횟수가 너무 많아 메모리 초과가 발생하였다.

 

정답

 

import java.util.*;
import java.math.*;

class Main{
	public static int MAX = 100000;
	public static boolean checked[] = new boolean[MAX+1];
	public static int min = Integer.MAX_VALUE;
	public static int methodCnt = 0;
	
	public static void main(String args[]){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		
		bfs(n, k);
		
		System.out.println(min);
		System.out.println(methodCnt);

	}
	
	public static void bfs(int n, int k) {
		Queue<Position> q = new LinkedList<>();
		q.add(new Position(n, 0));
		while(!q.isEmpty()) {
			Position now = q.poll();
			
			//System.out.println(now.x);
			if(now.x == k) {
				if(now.cnt < min) {
					methodCnt = 0;
					min = now.cnt;
				}
				if(now.cnt == min) {
					methodCnt++;
				}
				continue;
			}
			if(now.x != k) checked[now.x] = true;

			//분기 한정2
			if(now.cnt + 1 <= min) {
				if(now.x-1 >= 0 && !checked[now.x-1]) {
					q.add(new Position(now.x-1, now.cnt+1));
				}
				if(now.x+1 <= MAX && !checked[now.x+1]) {
					q.add(new Position(now.x+1, now.cnt+1));
				}
				if(now.x*2 <= MAX && !checked[now.x*2]) {
					q.add(new Position(now.x*2, now.cnt+1));
				}
			}
		}
	}
}

class Position{
	int x;
	int cnt;
	Position(int x, int cnt){
		this.x = x;
		this.cnt = cnt;
	}
}

 

위 코드에서 달라진 점은 우선 방문 후 checked에 표시하는 것이다.  이렇게 되면 한번에 큐에 담길 값들은 그 값이 같더라도 우선 큐에 들어갈 수 있게 된다. 즉 비용이 같은 경우는 같은 점으로 가더라도 큐에 들어갈 수 있다는 것이다.

 

같은 노드에 갈 때 비용이 같아야만 들어갈 수 있는 이유는, 어차피 비용이 다를 경우 더 큰 노드는 정답 후보에서 탈락이기 때문이다. 즉, 먼저 큐에 들어간 경우는 BFS이므로 항상 비용이 더 작은 경우이다. 이후 더 큰 비용으로 해당 노드를 방문해봤자, 해당 큰 비용의 노드가 할 수 있는 건 적은 비용이 했던 것을 답습할 뿐이다.  같은 것을 함에도 비용이 더 크므로 정답 후보에서 탈락이다. 그러므로 일단 최소의 비용으로 해당 노드에 도달할 경우 해당 노드 방문을 잠궈버리는 것이다. 

 

예를 들어.

0 → 1(1증가) →2(1증가) →3(1증가)

0 → 1(1증가) →2(2를 곱함) →3 (1증가)에서

1에서 2로 향하는 두 경우는 1에서 동시에 출발하기에 둘 다 큐에 들어갈 수 있다.