백준 알고리즘_13549_숨바꼭질3

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

문제 설명

이번엔 2X만큼 이동하는 것이 1초가 아닌 0초가 걸린다는 문제이다.

문제 풀이

처음엔 그냥 2*X 해줄때의 step만 카운트 하지않고 q에 넣어줬다.
주어진 예제인 5, 17 로 돌려보니 정답인 2가 나오길래 별 생각없이 제출했다. 그랬더니 틀렸다.

왜 틀렸는지 알기 위해서는 또 다른 예제가 필요했다.
이번엔 5 15 를 입력했는데 결과가 3이 나왔다. 원래는 2가 나와야 한다.

5 > 4 > 8 > 16 > 15 이렇게가 2 Step이다.

왜 2가 안나오고 3이 나오는지 알기 위해서 디버깅을 했다.
그랬더니... step이 3인 값이 2인 것보다 q에서 더 빨리 나오기 때문이었다.

즉, 'nowN == K' 지만 step은 최소가 "아닌" 것이 "먼저" 도달할 수 있다는 것이다.

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

따라서 기존의 이 부분을 수정해 줄 필요가 있었다.

if(n == K) {
	//System.out.println("n == K 일때 >> "+stepInfo.step);
	answerList.add(new answerCandidate(stepInfo.step));
}

고심한 결과, answerCandidate라는 클래스를 하나 더 만들 필요가 있었다. n == k일 때마다 List<answerCandidate> answerList 객체에 step을 저장했다.

//걸음수 오름차순 정렬하여 최소걸음수 찾기
Collections.sort(answerList, new Comparator<answerCandidate>(){
	@Override
	public int compare(answerCandidate o1, answerCandidate o2) {
		return Double.compare(o1.step, o2.step); //오름차순
	}
});
		
System.out.println(answerList.get(0).step);

그리고 main에서 오름차순으로 정렬해, 맨 앞에껄 출력했다.
그렇게 해주었는데도 여전히 3을 리턴하고 있었다..

도저히 이해가 안돼서 다시 디버깅을 돌렸다.
16 > 15로 가는 과정에서15가 이미 visited == true 상태였기 때문에 그냥 건너뛰어져버린 것이었다.

결국, 방문체크를 q에 넣은 직후 말고, 꺼낸 직후에 하는게 맞았다.

전체 코드

public class Practice2 {
	static int N;
	static int K;
	static boolean[] check = new boolean[100001];
	static int numberOfSearching = 0;
	static List<answerCandidate> answerList = new ArrayList<>();
	
	public static class StepInfo{
		int nowN;
		int step;
		
		public StepInfo(int nowN, int step) {
			this.nowN = nowN;
			this.step = step;
		}
	}
	
	public static class answerCandidate{
		int step;
		
		public answerCandidate(int step) {
			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);
		
		//걸음수 오름차순 정렬하여 최소걸음수 찾기
		Collections.sort(answerList, new Comparator<answerCandidate>(){
			@Override
			public int compare(answerCandidate o1, answerCandidate o2) {
				return Double.compare(o1.step, o2.step); //오름차순
			}
		});
		
		System.out.println(answerList.get(0).step);
	}

	private static void hideAndSeek(Queue<StepInfo> q) {
		
		while(!q.isEmpty()) {
			StepInfo stepInfo = q.poll();
			int n = stepInfo.nowN;
			
			check[n] = true;
			
			// 'nowN = K' 지만 step은 최소가 "아닌" 것이 "먼저" 도달할 수 있다.
			// 최소인 step을 언제 알수있지? '언제까지' 돌려야 하지? 무한정 돌릴순 없는거자나...
			if(n == K) {
				//System.out.println("n == K 일때 >> "+stepInfo.step);
				answerList.add(new answerCandidate(stepInfo.step));
			}
			
			// +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);
						q.add(nextStep);
						//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/0dfdaf29889f6030e2e952d120844b28