백준 1697. 숨바꼭질

🅰 백준 1697. 숨바꼭질

1697번: 숨바꼭질

✏️ 문제 풀이

• 큐를 이용하여 너비우선탐색을 해주었다.
• check변수를 이용하여 방문체크를 해서 방문한 곳은 다시 방문하지 못하도록 하였고, depth변수를 이용하여 몇번만에 동생을 찾았는지를 알기위해 선언하였다.
• 탐색을 하다가 동생(K)를 만나게 되면 반복문을 종료하도록 하였다.

✏️ 소스코드

package bruteforce;

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

public class Main_실버1_1697_손은성 {
	static int N, K, cnt;
	static final int max = 1000000; 
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		Queue<Integer> q = new LinkedList<Integer>();
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		int dist[] = new int[max];
		boolean check[] = new boolean[max];

		dist[N] = 0;
		check[N] = true;

		if (N == K)
			System.out.println(0);

		else {
			q.add(N);
			while (!q.isEmpty()) {
				int cur = q.poll();
				int next1 = 0, next2 = 0, next3 = 0;
				
				if (cur >= 1 && !check[cur - 1]) {
					next1 = cur - 1;
					check[next1] = true;
					dist[next1] += dist[cur]+1;
					if(next1 == K) {
						System.out.println(dist[next1]);
						break;
					}
					q.add(next1);
				}
				
				if (cur < K && !check[cur + 1]) {
					next2 = cur + 1;
					check[next2] = true;
					dist[next2] += dist[cur]+1;
					if(next2 == K) {
						System.out.println(dist[next2]);
						break;
					}
					q.add(next2);
				}
				
				if (cur < K && !check[cur * 2]) {
					next3 = cur * 2;
					check[next3] = true;
					dist[next3] += dist[cur]+1;
					if(next3 == K) {
						System.out.println(dist[next3]);
						break;
					}
					q.add(next3);
				}
			}
		}
	}

}

✏️ 소스코드

package bruteforce;

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

public class Main_실버1_1697_손은성_shorts{
	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);
		}
	}
}

 

✅ 후기

• 처음에는 큐를 이용한 방법으로 풀었는데, 나중 보니 dfs를 이용한 방식도 있어서 다시한번 작성해보았다.