백준 알고리즘_12851_숨바꼭질2

https://www.acmicpc.net/problem/12851

문제 풀이

숨바꼭질 문제에서 최단 거리를 요구했다면, 숨바꼭질2 문제는 최단 거리와 최단거리로 가는 방법의 수도 함께 요구한다.

전체 코드

public class Practice2 {
	static int N;
	static int K;
	static boolean[] check = new boolean[100001];
	static int numberOfSearching = 0;
	static int minStep = 0; 
	
	public static class StepInfo{
		int nowN;
		int step;
		
		public StepInfo(int nowN, int step) {
			this.nowN = nowN;
			this.step = step;
		}
	}
	
	public static void main(String[] args) {
		input();
		
		StepInfo stepInfo = new StepInfo(N, 0);
		
		Queue<StepInfo> q = new LinkedList<>();
		q.add(stepInfo);
		
		hideAndSeek(q);
		System.out.println(numberOfSearching);
	}

	private static void hideAndSeek(Queue<StepInfo> q) {
		
		while(!q.isEmpty()) {
			StepInfo stepInfo = q.poll();
			int n = stepInfo.nowN;
			check[n] = true;
			
			if(n == K && minStep == 0) {
				System.out.println(stepInfo.step);
				numberOfSearching++;
				if(numberOfSearching == 1) minStep = stepInfo.step;
				
			}else if(n == K && minStep >= stepInfo.step) {
				numberOfSearching++;
			}
			
			// +1, -1, *2 셋 중 어느 연산을 할 건지 탐색
			StepInfo nextStep;
			int tempN;
			for(int d = 0; d < 3; d++) {
				switch(d) {
				case 0:
					tempN = n;
					tempN += 1;
					if(tempN >= 0 && tempN < check.length && check[tempN] == false) {
						nextStep = new StepInfo(tempN, stepInfo.step + 1);
						q.add(nextStep);
						//check[tempN] = true;
					}
					
					break;
					
				case 1: 
					tempN = n;
					tempN -= 1;
					if(tempN >= 0 && tempN < check.length && check[tempN] == false) {
						nextStep = new StepInfo(tempN, stepInfo.step + 1);
						q.add(nextStep);
						//check[tempN] = true;
					}
					
					break;
					
				case 2:
					tempN = n;
					tempN *= 2;
					if(tempN >= 0 && tempN < check.length && check[tempN] == false) {
						nextStep = new StepInfo(tempN, stepInfo.step + 1);
						q.add(nextStep);
						//check[tempN] = true;
					}
					
					break;
					
				}
			}
			
		}
		
	}

	private static void input() {
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		K = sc.nextInt();
	}

}

풀이 방식

숨바꼭질 문제에서는 5 > 6 > 5 등 이미 나왔던 숫자로 되돌아가는 경우를 방지하기 위해 check 라는 배열로 중복을 금지했다.

하지만 숨바꼭질2 문제에서는 저 중복 방지를 어느정도 풀어줘야 다른 경우의 최단거리를 구할 수 있다.

for(int d = 0; d < 3; d++) {
	switch(d) {
	case 0:
		tempN = n;
		tempN += 1;
		if(tempN >= 0 && tempN < check.length && check[tempN] == false) {
			nextStep = new StepInfo(tempN, stepInfo.step + 1);
			q.add(nextStep);
            		check[tempN] = true;
		}
					
		break;
					
	case 1: 
		tempN = n;
		tempN -= 1;
		if(tempN >= 0 && tempN < check.length && check[tempN] == false) {
			nextStep = new StepInfo(tempN, stepInfo.step + 1);
			q.add(nextStep);
            		check[tempN] = true;
		}
					
		break;
					
	case 2:
		tempN = n;
		tempN *= 2;
		if(tempN >= 0 && tempN < check.length && check[tempN] == false) {
			nextStep = new StepInfo(tempN, stepInfo.step + 1);
			q.add(nextStep);
            		check[tempN] = true;
		}
					
		break;
					
	}

이전 숨바꼭질 문제에서는check[tempN] = true; 로 중복체크를 큐에 넣고 난 이후에 해주었다.

private static void hideAndSeek(Queue<StepInfo> q) {
		
	while(!q.isEmpty()) {
		StepInfo stepInfo = q.poll();
		int n = stepInfo.nowN;
		check[n] = true;
            	...

하지만 숨바꼭질2 에서는 큐에서 값을 빼내고 나서 해주었다.

둘이 무슨 차이가 있냐면, 전과 같이 하면 새로운 수를 큐에 넣음과 동시에 다른 경우에선 해당 수를 뽑을 수 없게 된다.
그에 비해, 지금과 같이 하면 다른 경우에서도 해당 수를 뽑을 수 있게 되며, 최단경로에 대해 여러 경우가 생겨날 수 있는 것이다.

예를 들어 설명하면 이렇다.
현재 진행상태가 5 > 6이라고 해보자.
6 에서는 7 5 12 총 세가지 경우로 나아갈 수 있다. 저 중 5 를 중복체크가 되어있으므로 제외하면 7 과 12 만 남게 된다.

여기서, 이전 숨바꼭질 문제에서는 7 과 12 를 큐에 넣자마자 중복체크를 해줌으로써, 다른 경우에서 7 과 12 로 나아갈 수 없게 하였다.

하지만 숨바꼭질2 에서는 7 12 를 큐에 넣은 후, 큐에서 빼낼 때 중복체크를 하므로 다른 경우에서도 7 12 가 들어간 여러 경우가 생겨나게 되는 것이다.

if(n == K) {
	System.out.println(stepInfo.step);
	break;
}

또한, q 에서 값을 빼낸 후 기존 숨바꼭질 문제에서

if(n == K && minStep == 0) {
	System.out.println(stepInfo.step);
	numberOfSearching++;
    
	if(numberOfSearching == 1) minStep = stepInfo.step;
				
}else if(n == K && minStep >= stepInfo.step) {
	numberOfSearching++;
}

현재 위치가 동생의 위치인지 검사해주는 로직을 위와 같이 수정하였다.

맨 처음 최단거리로 도달한 경우의 step 을 minStep 에 저장한다. 그리고 후에 목표지점에 도달했지만 앞서 저장한 최단거리와 같거나 더 작은 경우에만 count 해준다.

이렇게 하지 않으면, 여러 경우의 최단경로가 아니라 목표지점까지의 모든 경로가 구해지는 거 같다.

Git gist 주소

https://gist.github.com/ysyS2ysy/989d1c3b59584dd5f56f94e112d78c70