백준 알고리즘 - 13913_숨바꼭질4

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

문제 설명

최단거리의 경로까지 구해야 하는 문제이다.

문제 풀이

숨바꼭질 시리즈를 풀면서 가장 구하고 싶었던게, 최단거리의 경로까지 구하는 것이었다. 그런데 숨바꼭질4에서 딱 이러한 점을 요구하고 있어서 놀랐고, 더욱 풀고싶었다.

처음에 각 큐의 경로를 어떻게 구할지 엄청나게 고민했다. 그래서 생각해낸 방법이...

클래스 StepInfo 에 List<Integer>객체인 route 를 추가해주는것이었다. 저 route 객체에 그동안 지나온 위치를 저장한다.
하지만 각각의 q말고 모든 q에서 꺼낸 값들이 저장되는 문제가 생겼다.ㅠ

그래서 몇시간을 다시 고민하기 시작했다.ㅠ 결국 여러방법을 시도해봤으나 실패해서 인터넷에 나와있는 풀이를 참고했다.

바로 배열에 저장하는 것이었다.
나는 계속 리스트에 저장할 생각만 했어서, 배열에 저장할 생각은 꿈에도 못했다. 앞으로도 좀 더 노력해야 할듯 하다ㅠ

static int[] route = new int[100001];

일단 전역변수로 배열을 선언해주었다.

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);
			route[tempN] = n;
			check[tempN] = true;
		}
					
		break;

아직 방문하지 않은 수를 q에 넣을 때, 방문기록을 저장하는 route에도 저장해준다.
5 > 6 이라 가정하면, route[6] = 5 가 저장된다.

즉, 문제 예제 5 17 이 입력되면, 5 > 10 > 9 > 18 > 17 순으로 방문하는 것이 최단경로인데.

route[10] = 5
route[9] = 10
route[18] = 9
route[17] = 18

이런식으로 route에 저장된다.


그리고나서 현재 위치 n이 동생의 위치인 K에 도달할 경우, route[N]에서 부터 시작해, 서로 가리키고 있는 값을 출력해냈다.

if(n == K){
      System.out.print(route[N] + " ");
      int idx = route[N];

      for(int i = 0; i < stepInfo.step; i++){
          System.out.print(route[idx] + " ");
              idx = route[idx];
      }
 }

즉, route[5] 부터 시작해서, 그 값을 idx에 담아주고, 그 다음은 route[idx]를 출력하는 것을 최단거리 수만큼 반복했다.

그랬더니 5와 6이 핑퐁되는 현상이 발생했다 ...
route[5] = 6 이고, route[6] = 5 였기 때문에 생긴 현상이었다..

저거때문에 몇시간을 헤맸는지 모른다ㅠ
분명 5에서 4가 되는게 최단거리의 경로일텐데,, 5 에서 6이 된다고 생각했었으니 말이다.

하지만, 여기서 route의 의미를 다시한번 되짚고 갈 필요가 있었다.

route[tempN] = n 의 의미란, tempN > n 이 아니라
반대로 n > tempN 으로 간다는 의미였는데, 헷갈려서 기본적은 실수를 하고 있었다ㅠ

즉, route[N]으로 시작하는 것은 시작점에서 출발하겠다는 의미가 아니라 시작점으로 가겠다 였다...ㅠㅠㅠ

if(n == K) {
	System.out.println(stepInfo.step);
				
	Stack<Integer> stack = new Stack<>();
	stack.push(route[K]);
	int idx = route[K];
				
	for(int i = 0; i < stepInfo.step - 1; i++){
		stack.push(route[idx]);
		idx = route[idx];
	}
				
	while(!stack.isEmpty()) {
		System.out.print(stack.pop()+" ");
	}
	System.out.print(K);
}

따라서 아까처럼 시작위치 N 에서부터 출력하는 것이 아닌, 동생의 위치 K에서부터 경로를 따라 출력해주었다.

거꾸로 따라가기 때문에!! 출력은 시작위치에서 하기 위해서 Stack을 사용하였다!

하지만 문제점이 발생했다 ㅠ
맞게 풀었다고 생각했는데, 막상 제출해보니 틀렸다는 결과가 나오고 있었다.
여기서 또 몇 시간을 잡아먹었다ㅠ
반례 이것저것 넣어보았지만 맞는 결과값이 출력되고 있어서 더욱 멘붕이었다...ㅠ

몇 시간을 까먹고나니 눈이 너무 아파서 빠질것같아 다른 사람들에게 도움을 요청했다.

그 결과, 5 5 같이 N과 K가 같은 경우에 0 과 5 하나만 나와야 하는데, 출력이 이상하게 되는 것이었다.

알고보니 N과 K가 같은 케이스는, 바로 정답만 출력하고 끝나야 하는데, 그러지 않고 그 아래까지 쭉 돌아가버려서 저런 이상한 결과가 발생했던 것이었다.

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

따라서, 위와 같이 N과 K가 같은 케이스일때의 로직도 추가해줌으로써 해결했다ㅠ
정말 힘들었던 과정이었다..ㅠㅠㅠㅠ

이렇게 고생하며 느꼈던 점은, 최소 최대 케이스를 꼭 체크해봐야 한다는 것과 가장 간단한 케이스 (오늘같은) 도 확인해봐야 한다는 것을 깨닫게 되었다ㅠㅠㅠㅠ

전체 코드

public class Practice2 {
	static int N;
	static int K;
	static boolean[] check = new boolean[100001];
	static int[] route = new int[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();
		
		List<Integer> records = new ArrayList<>();
		records.add(N);
		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;
			
			//check[n] = true;
			
			if(n == K) {
				if(N == K) {
					System.out.println(stepInfo.step);
					
					System.out.println(N);
					return;
				}
				System.out.println(stepInfo.step);
				
				Stack<Integer> stack = new Stack<>();
				stack.push(route[K]);
				int idx = route[K];
				
				for(int i = 0; i < stepInfo.step - 1; i++){
					stack.push(route[idx]);
					idx = route[idx];
				}
				
				while(!stack.isEmpty()) {
					System.out.print(stack.pop()+" ");
				}
				System.out.print(K);
			}
			
			// +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);
						route[tempN] = n;
						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);
						route[tempN] = n;
						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);
						route[tempN] = n;
						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/2eaf04db26587b2ee4e95a99e95573ad