[JAVA] 백준 1697번_숨바꼭질

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

1697번: 숨바꼭질

---

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int answer, now, target;
    static int[] time = new int[100001]; //범위까지 인덱스 설정
    static boolean[] visit = new boolean[100001];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        now = sc.nextInt();
        target = sc.nextInt();
        if(now >= target) //순간 이동은 x2만 가능하므로, 수빈이가 더 앞에 있는 경우 뒤로 걷기만 가능
            answer = Math.abs(now - target);
        else {
            chase(now);
            answer = time[target];
        }
        System.out.println(answer);
    }

    private static void chase(int start) { //가능한 모든 방법에 대해 bfs 진행
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visit[start] = true;
        while (!queue.isEmpty()) {
            int now = queue.poll();
            if (now == target) return; //목표에 도착하면 탐색 끝(최선이므로)
            int cnt = time[now] + 1;
            if(now > 0 && !visit[now-1]){
                time[now - 1] = cnt;
                visit[now - 1] = true;
                queue.add(now - 1);
            }
            if(now < 100000 && !visit[now+1]){
                time[now + 1] = cnt;
                visit[now + 1] = true;
                queue.add(now + 1);
            }
            if(now <= 50000 && !visit[2*now]){
                time[2 * now] = cnt;
                visit[2 * now] = true;
                queue.add(2 * now);
            }
        }
    }
}

 

💡 BFS 사용

처음엔 재귀 용법으로 값을 저장해나가는 방식으로 수행했지만 스택 오버플로우 발생
  →  재귀 대신 bfs로 방향 변경

 

효율 개선

• 뒤로 갈 수록 cnt값이 커지는 것은 필연적이므로 ... 굳이 기존 time값과 비교할 필요 없이 방문 배열로 거르자
• 불필요하게 값을 저장하는 배열 길이를 늘리지 말고, if문에서 다음 인덱스로 방문 검사하기 전, 이동한 인덱스가 유효 범위인지 체크하는 것을 선 조건으로 넣어주기

변경 전 코드 (bfs)

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int answer, now, target;
    static int[] time = new int[400001];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        now = sc.nextInt();
        target = sc.nextInt();
        if(now >= target)
            answer = Math.abs(now - target);
        else {
            Arrays.fill(time, Integer.MAX_VALUE);
            time[now] = 0;
            chase(now);
            answer = time[target];
        }
        System.out.println(answer);
    }

    private static void chase(int start) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        while (!queue.isEmpty()) {
            int now = queue.poll();
            if (now > 200000) continue;
            int cnt = time[now] + 1;
            if(now > 0 && time[now-1] > cnt){
                time[now-1] = cnt;
                queue.add(now - 1);
            }
            if(time[now+1] > cnt){
                time[now+1] = cnt;
                queue.add(now + 1);
            }
            if(time[2*now] > cnt){
                time[2*now] = cnt;
                queue.add(2 * now);
            }
        }
    }
}