★백준/1697 숨바꼭질 / bfs

숨바꼭질 성공다국어

한국어   

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

178291

51168

32156

25.208%

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

예제 입력 1 복사

5 17

예제 출력 1 복사

4

---

풀이

1. 메모리초과

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


    /*
       bfs를 이용해서 구현한다. 현재 위치에서 *2,+1,-1한 값들을 다 큐에 넣는식으로 , 한번 이동했을경우 모든경우 2번 이동했을경우와 같이 한번씩 이동하면서 모든경우를 살펴보면서 동생의 위치를 만났을때가
       가장적게 이동한 횟수가 될것이다, 시간을 저장하는 변수는 큐로 같이 전달한다. (위치,시간)

       dfs는 하나의 경우를 끝까지 보므로, 무한루프에 빠질수있다. 동생의 위치를 넘었을때 멈춘다고해도, -1이라는 경우가 존재하므로 쉽지않을거같다.
     */

    static int n,k;


    public static void main(String[] args) throws IOException {

        input();
        solve();

        bw.flush();
        bw.close();

    }

    static void input() throws IOException {
        int[] input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        n = input[0];
        k = input[1];
    }

    static void solve() throws IOException {
        bfs();
    }

    static void bfs() throws IOException {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{n, 0});

        while (!q.isEmpty()) {
            int[] current = q.poll();
            int currentPosition = current[0];
            int currentTime = current[1];
            if (currentPosition == k) {
                bw.write(currentTime+"");
                return;
            }

            q.add(new int[]{currentPosition+1,currentTime+1}); // 1초뒤 앞으로 한칸 이동한경우
            q.add(new int[]{currentPosition-1,currentTime+1});// 1초뒤 뒤로 한칸 이동한경우
            q.add(new int[]{currentPosition*2,currentTime+1});// 1초뒤 순간이동한 경우
        }

    }

}

2. 큐에서 꺼내고 방문처리,  다음위치 필터링

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;


public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


    /*
       bfs 최단시간을 찾는문제.
       이미 들렸던 위치는 큐에 다시 넣는일이 없어야한다. bfs는 시간순서대로 이동하는데(트리의 레벨단위 이동처럼) 이미 들렸던곳이라는것은 현재보다 이른시간에 들렸다는것이므로 최소시간이 될 수 없는경우다.
       다음으로 확인해볼 위치가 범위를 넘는지, 방문했던곳인지 체크한다.
       이런 경우에 대해 조건처리를 해줘야 메모리초과가 발생하지않는다.
     */

    static int n,k;
    static final int maxRange = 100000;
    static boolean[] visited = new boolean[maxRange+1];


    public static void main(String[] args) throws IOException {

        input();
        solve();

        bw.flush();
        bw.close();

    }

    static void input() throws IOException {
        int[] input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        n = input[0];
        k = input[1];
    }

    static void solve() throws IOException {
        bfs();
    }

    static void bfs() throws IOException {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{n, 0});
        visited[n] = true;

        while (!q.isEmpty()) {
            int[] current = q.poll();
            int currentPosition = current[0];
            int currentTime = current[1];
            visited[currentPosition] = true;
            
            if (currentPosition == k) {
                bw.write(currentTime+"");
                bw.flush();
                System.exit(0);
            }

            //수에범위가 벗어나는지를 먼저 체크해줘야한다. 그래야 인덱스 에러가 발생하지않음.
            if (currentPosition + 1<=maxRange && !visited[currentPosition + 1] ) {
                q.add(new int[]{currentPosition+1,currentTime+1}); // 1초뒤 앞으로 한칸 이동한경우
            }
            if ( (currentPosition-1) >= 0 && !visited[currentPosition - 1]) {
                q.add(new int[]{currentPosition-1,currentTime+1});// 1초뒤 뒤로 한칸 이동한경우
            }
            if (currentPosition * 2 <= maxRange && !visited[currentPosition * 2]) {
                q.add(new int[]{currentPosition * 2, currentTime + 1});// 1초뒤 순간이동한 경우
            }

        }

    }

}

3. 큐에서 꺼냈을때 방문처리 하지않고 , 큐에 넣기전 방문처리

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;


public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int n,k;
    static final int maxRange = 100000;
    static boolean[] visited = new boolean[maxRange+1];


    public static void main(String[] args) throws IOException {

        input();
        solve();

        bw.flush();
        bw.close();

    }

    static void input() throws IOException {
        int[] input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        n = input[0];
        k = input[1];
    }

    static void solve() throws IOException {
        bfs();
    }

    static void bfs() throws IOException {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{n, 0});
        visited[n] = true;

        while (!q.isEmpty()) {
            int[] current = q.poll();
            int currentPosition = current[0];
            int currentTime = current[1];
            
            
            if (currentPosition == k) {
                bw.write(currentTime+"");
                bw.flush();
                System.exit(0);
            }

            //수에범위가 벗어나는지를 먼저 체크해줘야한다. 그래야 인덱스 에러가 발생하지않음.
            if (currentPosition + 1<=maxRange && !visited[currentPosition + 1] ) {
                visited[currentPosition + 1] = true;
                q.add(new int[]{currentPosition+1,currentTime+1}); // 1초뒤 앞으로 한칸 이동한경우
            }
            if ( (currentPosition-1) >= 0 && !visited[currentPosition - 1]) {
                visited[currentPosition - 1] = true;
                q.add(new int[]{currentPosition-1,currentTime+1});// 1초뒤 뒤로 한칸 이동한경우
            }
            if (currentPosition * 2 <= maxRange && !visited[currentPosition * 2]) {
                visited[currentPosition *2] = true;
                q.add(new int[]{currentPosition * 2, currentTime + 1});// 1초뒤 순간이동한 경우
            }

        }

    }

}