[백준 / Java] 1697번 숨바꼭질

사용한 알고리즘 (BFS)

BFS

https://cobi-98.tistory.com/36

[필수 알고리즘] BFS 너비 우선 탐색 (Queue 구조) 이해

 

🔒 1697번 숨바꼭질

✔ 문제 설명

🚩 요구사항 분석

• 이동할 수 있는 경우의 수 배열로 지정
• 시간을 세기 위한 변수 (배열)

 

🔑 문제풀이

해당 문제를 풀기 전 5-10-9-18-17 순으로 4초 만에 동생을 찾을 수 있다.라는 힌트를 보고

5-10-9-18-17는

5-4-8-16-17 도 될 수 있다는 가정을 둠으로써 수빈이가 걷는 조건인 x-1과 x+1의 조건이 상관없다고 느껴졌다.

 

그렇기에 동생의 위치를 보고 동생의 위치가 홀수면 -1 짝수면 나누기 2를 하면서

수빈이랑 같아지면 count를 출력하는 방법을 사용해 보았다.

// 시간초과 코드, 알고리즘 x
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 Main {
    
    public static int N;
    public static int K;
    public static int count;
    public static Queue<Integer> queue = new LinkedList<Integer>();
    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());
        count = 0;

        while(N != K){
            if (K%2 == 0){
                K = K /2;
            }else if(K%2 == 1){
                K = K+1;
            }
            count = count+1;
        }

        System.out.println(count);
    }


}

 

해당 결과는 시간초과.

 

해당문제는 count를 하기 위한 배열과 모든 방식을 검색할 수 있는 알고리즘이 필요했다.

그렇기에 bfs를 사용해 최단거리를 구할 수 있는 방식을 이용했다.

bfs 방식으로 검색해 나감

수빈이가 이동할 수 있는 경우를 확인하면서 찾게 된다면, 그 거리가 최소거리가 될 것이다.

 이동할 수 있는 조건을 for문으로 체크하며 동생을 찾는다면 retrun 해준다.

 

수빈이가 다음으로 건너는 거리가 (0 ≤ N ≤ 100,000)이고 다음에 건너는 경우가 건넌 적이 없다면(count [next] ==0)

count라는 배열로 숫자를 세는 방식으로 진행했다.

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 Main {
    public static int N;
    public static int K;
    public static int[] dMove = {-1, 1, 2};
    public static int[] count;
    public static Queue<Integer> queue = new LinkedList<Integer>();

    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());
        count = new int[100001];

        count[N] = 1;
        queue.add(N);

        if (N == K) {
            System.out.println(0);
        } else {
            bfs();
        }
    }

    public static void bfs() {

        while (!queue.isEmpty()) {
            int temp = queue.poll();

            for (int i = 0; i < 3; i++) {
                int next;
                if (i == 2) {
                    next = temp * dMove[i];
                } else {
                    next = temp + dMove[i];
                }

                if (next == K) {
                    System.out.println(count[temp]);
                    return;
                }

                if (next >= 0 && next < count.length && count[next] == 0) {
                    queue.add(next);
                    count[next] = count[temp] + 1;
                }
            }

        }

    }


}