[Java]백준 BaekJoon.AC 13549 : 숨바꼭질3 (너비우선탐색-bfs, Queue)

 

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

13549번: 숨바꼭질 3

 

 

2*X의 위치로 이동할 땐 0초가 소요된다는게 숨바꼭질2와 다른 점이다.

그리고 그 방법이 몇 가지인지 구하지 않아도 된다. 가장 작은 시간값이 무엇인지만 구하면 된다.

 

이미 푼 숨바꼭질2 코드를 보고 베끼려 하지 않았다.

그렇지만 아무래도 파생된 문제이기 때문에 기본적인 큰 틀은 같았다.

 

소요시간이 0초인 2*X를 어떻게 구현할지 고민을 많이 했다.

이 경우엔 시간이 들지 않으니 일단 2*X를 모두 깔아두고 X-1과 X+1을 적용하는 방법을 택했다.

그리고 기존 틀은 같되, 본래 값보다 작은 시간이 발생한다면 값을 리뉴얼 주는 형식을 이용했다.

값이 얼추 나오길래 채점했는데, 결과는 시간초과.

 

<틀린코드>

public class Main {
	static int S, D;
	static int[] arr = new int[100001];
	static int time = 999999;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		S = Integer.parseInt(st.nextToken());
		D = Integer.parseInt(st.nextToken());

		if(S>=D) {
			time = S-D;
		}else {
			Arrays.fill(arr, -1);
			cal();
		}
		
		System.out.print(time);	
		
	}
	
	public static void cal() {
		
		Queue<Integer> queue = new LinkedList<>();
		
		queue.add(S);
		arr[S] = 0;
		
		while(!queue.isEmpty()) {
			int q = queue.poll();
			int X;
			
			if(time < arr[q]) {
				continue;
			}
			
			int t = q;
			while(2*t <= 100000) {
				if(2*t > D+(D+S)/2) break;
				
				if(arr[2*t]==-1 || arr[2*t] > arr[t]) {
					arr[2*t] = arr[t];
					if(2*t==D) {
						time = arr[2*t];
						break;
					}
					queue.add(2*t);
				}
				t = 2 * t;
			}
			
			for(int i=0; i<2; i++) {
				if(i==0)   X = q - 1;
				else       X = q + 1;
				
				if(X<0 || X>100000) continue;
				
				if(arr[X]==-1 || arr[X]-1>arr[q]) {
					arr[X] = arr[q] + 1;
					if(X==D) {
						time = arr[X];
						continue;
					}
					queue.add(X);
				}
				
			}
			
		}
	}
	
}

 

이유가 뭘까 싶어 다른 사람들의 코드를 참고했다.

크게 다른 점은 없었는데, 하나 다른점은 리뉴얼을 하지 않는다는 거였다.

전보다 작은 시간값을 가지면 어쩌려고 리뉴얼을 하지 않은 걸까?

 

그런데, 내가 일일이 직접 손으로 문제를 풀었는데, 재방문 자체가 없던 걸 발견했다.

왜 겹치는 부분이 없고 재방문 하는 일이 없을까? visit 배열을 만들지 않고 리뉴얼 방법을 택했는데, 리뉴얼 자체를 안하는거 있지..?

 

한참을 고민하다, 내가 애초에 '먼저 2*X를 전부 깔아놓기'를 택했다는 데에서 이유를 발견했다.

시간 0이 가능한 모든 곳(시작점에서부터 계속 2*X)을 이미 다 방문시키고,

시작 점에서 좌우로 한칸 움직인 후에도 시간 1이 가능한 모든 곳(그 칸에서부터 계속 2*X)을 입력하는 코드를 애초에 짰더라...ㅋㅋ;;

 

즉, 애초에 queue에는 시간이 작은 순서대로 추가됐기 때문에 리뉴얼 할 일 자체가 없었던 거다....!

그러니 결과값을 따로 리뉴얼할 필요도 없고, 그냥 동생이 있는 칸의 시간값을 얻게 된다면 그 값이 최솟값이자 정답인 것이다.

이전 값과 비교할 필요가 없다. 동생 값과 같다면 바로 return해줘도 된다.

 

조금 변형했더니 여전히 시간초과길래 몽땅 줄여줬다... 까다로운 녀석..

그래도 방식 자체는 틀리지 않아 만족스럽다. 디테일을 놓친건 아깝지만.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int S, D;
	static int[] arr = new int[100001];
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		S = Integer.parseInt(st.nextToken());
		D = Integer.parseInt(st.nextToken());

		if(S>=D) {
			arr[D] = S-D;
		}else {
			Arrays.fill(arr, -1);
			cal();
		}
		
		System.out.print(arr[D]);	
		
	}
	
	public static void cal() {
		
		Queue<Integer> queue = new LinkedList<>();
		
		queue.add(S);
		arr[S] = 0;
		
		while(!queue.isEmpty()) {
			int q = queue.poll();
			int X;
			
			int t = q;
			while(2*t <= 100000 && arr[2*t]==-1) {
				
				arr[2*t] = arr[t];
				
				if(2*t==D) return;
					
				queue.add(2*t);
				t = 2 * t;
			}
			
			for(int i=0; i<2; i++) {
				if(i==0)   X = q - 1;
				else       X = q + 1;
				
				if(X<0 || X>100000) continue;
				
				if(arr[X]==-1) {
					arr[X] = arr[q] + 1;
					if(X==D) return;
					queue.add(X);
				}
				
			}
			
		}
	}
	
}