백준 알고리즘_1697_숨바꼭질

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

문제 설명

수빈이의 위치는 N, 동생의 위치는 K이다.
수빈이는 한 걸음에 N+1, N-1, 2N의 세 가지 방향으로 움직일 수 있다.
수빈이는 최소 몇걸음 만에 동생을 찾을 수 있는가?

문제 풀이

이 문제는 최소 걸음을 구해야 하므로 BFS로 풀어야 한다.
테스트케이스 예제로 N = 5, K = 17 이 주어졌다.

이렇게 쭉 나아가다 보면 4번째 걸음에서 17이 나와 종료될 것이다.

public static class StepInfo{
		int nowN;
		int step;
		
		public StepInfo(int nowN, int step) {
			this.nowN = nowN;
			this.step = step;
		}
	}

그래서 처음에 클래스 구조에 현재 위치 nowN 과 현재 몇걸음인지 나타내는 step 을 선언했다.

// +1, -1, *2 셋 중 어느 연산을 할 건지 탐색
StepInfo nextInfo;
int tempN;

for(int d = 0; d < 3; d++) {
	switch(d) {
	case 0: 
		tempN = n;
		tempN += 1;
					
		nextInfo = new StepInfo(tempN, stepInfo.step + 1);
		q.add(nextInfo);
					
		break;
					
	case 1: 
		tempN = n;
		tempN -= 1;
				
		nextInfo = new StepInfo(tempN, stepInfo.step + 1);
		q.add(nextInfo);
					
		break;
					
	case 2:
		tempN = n;
		tempN *= 2;

		nextInfo = new StepInfo(tempN, stepInfo.step + 1);
		q.add(nextInfo);
					
		break;
	}
}

그리고 +1 -1 *2 세 가지 방향으로 나아가 큐에 쌓다가

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

현재 위치 n 이 동생의 위치 K와 일치하면 정답을 출력하는 로직을 짰다.
그런데 이렇게 하면 메모리 초과가 나게 된다.

왜냐하면 위의 그림을 보게 되면 5 > 6 > 5 처럼, 왔던 수를 또 호출하는 경우가 생기기 때문이다.
우리는 최소 걸음을 구하는 것이기 때문에 이미 왔던 위치로 되돌아가면 절대 안된다.

static boolean[] check = new boolean[100001];

따라서 다음과 같이 check 배열을 할당하여 왔던 위치로 되돌아가지 않게 해줘야 한다.

전체 코드

package backJoon_1697_HideAndSeek;
import java.util.*;
/*
 * 
 * 백준알고리즘
 * 1697. 숨바꼭질
 * https://www.acmicpc.net/problem/1697
 * 2021-03-28
 * 
 * */
public class Practice2 {
	static int N;
	static int K;
	static boolean[] check = new boolean[100001];
	
	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);
	}

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

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

}

Git gist 주소

https://gist.github.com/ysyS2ysy/d63568b4a11c80732f8702df1a578b27