[BaekJoon] 백준 1697번 _ 숨바꼭질 for JAVA _ BFS 알고리즘

 

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

1697번: 숨바꼭질

 

 

 

문제

 

 

 

---

 

BFS로 풀어야하는 문제이다.

 

 

풀이 방법은

 

 

 

 

 

 

 

문제에 나온 순서만 살펴보면 위 그림처럼 나올 것이다.

 

 

next == K 인지 확인하고 맞다면 check[temp] 를 출력하면 된다.

 

 

 

 

코드

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


public class Baek1697 { // BFS
	public static int N, K;
	public static int count[] = 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(), " ");
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		if(N == K) System.out.println("0"); // 이거 안하면 틀림 bfs() 가자마자 +1-1*2 갈기기때문
		else
			bfs(N);
	}
	
	public static void bfs(int N) {
		Queue<Integer> queue = new LinkedList<>();
		queue.offer(N);
		count[N] = 1;
		
		while(!queue.isEmpty()) {
			int temp = queue.poll();
			
			for(int i = 0; i < 3; i++) {
				int next = 0;
				
                //하나씩 확인해보자
				if(i == 0) next = temp + 1;
				else if(i == 1) next = temp - 1;
				else next = temp * 2;
				
				if(next == K) {
					System.out.println(count[temp]);
					return;
				}
				
                // 범위 확인하고 안넣어본 것만 큐에 넣자
				if(next >= 0 && next <= 100000 && count[next] == 0) {
					queue.offer(next);
					count[next] = count[temp] + 1;
				}
				
			}
		}
	}
}

 

 

 

 

 

성능

 

 

 

 

---

 

 

다른 사람 코드를 살펴보겠다.

 

 

 

 

https://www.acmicpc.net/source/16748582

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);
		}
	}
}

 

 

 

TTok TTok 하신분..... 흠...

 

 

 

그냥 그렇구나 하고 넘어감