BFS - 백준1697 숨바꼭질

처음 시도에는 단순한 알고리즘으로 풀 수 있다고 생각해서 다음과 같은 풀이를 생각했다.

처음 케이스 판별
1. 수빈이 동생보다 뒤에 있는 경우? -1만 반복
2. 앞에있는 경우? 아래 실행
판별후
1. 거리차가 x보다 큰 경우 -> 순간이동
2. 거리차가 x보다 작은 경우 ->
2-1. 동생 전 인 경우 -> +1
2-2. 동생 뒤 인 경우 -> -1
while(x = 동생 일때까지) // 시간 + 1

하지만 이 풀이는 아주 적은 테스트케이스만 통과되었다. 왜 그런지는 예제 테스트케이스를 위 알고리즘에 따라 생각해보면 알 수 있다.

이 문제는 BFS문제로 분류되어 있다.
따라서 풀이는 다음과 같다.

• 지금까지의 BFS문제는 상하좌우를 Queue에 넣으며 실행했지만, 이 문제의 경우엔 x-1, x+1, 2*x를 Queue에 넣으며 실행하는 방법을 사용하는 문제였다.

참고 및 주의 사항

• 방문한 곳을 표시하기 위해 마찬가지로 배열을 사용한다.
• 방문한 곳과 배열의 범위를 벗어나지 않는 지를 체크해준다.
• 코드를 보면 방문하지 않은 곳은 배열의 초기값 0으로 사용하는데, 시작지점의 시간도 0이므로 재방문하지 않기 위해 처리해준다.

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

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n, k;
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        
        int[] arr = new int[2000000];
        Queue<Space> queue = new LinkedList<>();
        
        Space subin = new Space(n, 0);
        arr[subin.position] = subin.time;
        queue.add(subin);
        int answer = 0;
        while(!queue.isEmpty()){
            Space nowSpace = queue.poll();
            if(nowSpace.position == k){
                answer = nowSpace.time;
                break;
            }
            
            int nextTime = nowSpace.time+1;
            
            int frontPos = nowSpace.position-1;
            int backPos = nowSpace.position+1;
            int doublePos = nowSpace.position*2;
            
			if(frontPos >= 0){
                if(arr[frontPos] == 0 && frontPos != n){
                    arr[frontPos] = nextTime;
                    queue.add(new Space(frontPos, nextTime));
                }
            }
            if(backPos < arr.length){
            	if(arr[backPos] == 0 && backPos != n){
                	arr[backPos] = nextTime;
                	queue.add(new Space(backPos, nextTime));
            	}
            }
            if(doublePos < arr.length){
            	if(arr[doublePos] == 0 && doublePos != n){
                	arr[doublePos] = nextTime;
                	queue.add(new Space(doublePos, nextTime));
                }
            }
        }
        System.out.println(answer);
        
    }
    static class Space{
        int position;
        int time;
        Space(int pos, int t){
            position = pos;
            time = t;
        }
    }
}