[백준] 1697 : 숨바꼭질

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

1697번: 숨바꼭질

숨바꼭질 3에서 순간이동도 시간을 적용시켜주면 되는 문제였다.

 

내 코드

메모리 : 18436 KB

시간 : 164 ms

코드길이 : 1488 B

 

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 N;
	static int K;
	static int result;
	static int[] time = new int[100001];
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		Arrays.fill(time, Integer.MAX_VALUE);
		
		if(N == K)
			result = 0;
		else {
			findSister();
		}
		
		sb.append(result);
		System.out.print(sb);
	}
	
	public static void findSister() {
		Queue<Integer> queue = new LinkedList<>();
		time[N] = 0;
		queue.add(N);
		
		while(!queue.isEmpty()) {
			int now = queue.poll();
			//동생을 잡으면
			if(now == K) {
				result = time[K];
				return;
			}
			//앞으로 걷기
			if(now + 1 <= 100000 && time[now] + 1 < time[now + 1]) {
				time[now + 1] = time[now] + 1;
				queue.add(now + 1);
			}
			//뒤로 걷기
			if(now - 1 >= 0 && time[now] + 1 < time[now - 1]) {
				time[now - 1] = time[now] + 1;
				queue.add(now - 1);
			}
			//순간이동
			if(2 * now <= 100000 && time[now] + 1 < time[2 * now]) {
				time[2 * now] = time[now] + 1;
				queue.add(2 * now);
			}
		}
		return;
	}


}

 

1등 코드

메모리 : 11512 KB

시간 : 72 ms

코드길이 : 890 B

 

[1등 코드]

import java.io.*;
import java.util.*;

public class Main{
	static int answer;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());		//수빈이 위치
		int k = Integer.parseInt(st.nextToken());		//동생 위치
		answer = Integer.MAX_VALUE;
		
		dfs(n, k, 0);
		System.out.println(answer);
	}
	
	public static void dfs(int n, int k, int count) {		//수빈이위치, 동생위치, 카운트
		if( n >= k ) {
			count += n - k;
			if( answer > count ) {
				answer = count;
			}
			return;
		}
		
		dfs(n, n, count + k - n);
		if( n == 0 ) {
			n = 1;
			count++;
		}
		
		if( k % 2 == 1 ) {
			dfs(n, k + 1, count + 1);
			dfs(n, k - 1, count + 1);
		}		
		else {
			dfs(n, k / 2, count + 1);
		}
	}
}