백준-1697번/숨바꼭질(java)

 

 

문제 이해

 

기존의 BFS 문제들이랑 크게 다를것은 없었다. 이동 경로만 잘 생각해주면 그렇게 어려운 문제는 아니다.

 

이동 경로 

1) 1칸 앞으로 이동

2) 1칸 뒤로 이동

3) 현 위치 * 2 만큼 이동

 

이러한 이동을 구현하기 위해 move 배열 생성

static int[] move = {1,-1,2};

 

이동 규칙

1) 방문했던 곳을 방문X

2) 이동에 걸리는 시간을 출력해야 하므로 이동 할때마다 시간 +1

3) 방문했다면 visit 배열에 방문을 표시

 

문제 풀이

 

public static void BFS(int now){
    Queue<Integer> queue = new LinkedList<>();
    queue.add(now);
    visit[now]=true;

    while(!queue.isEmpty()){
        int point = queue.poll();
        for(int i=0; i<3; i++){
            if(i==2){
                int next = point*2;
                if(next<0 || next>100000){
                    continue;
                }
                if(visit[next]){
                    continue;
                }
                queue.add(next);
                arr[next]=arr[point]+1;
                visit[next]=true;

            }
            else {
                int next = point + move[i];
                if(next<0 || next>100000){
                    continue;
                }
                if(visit[next]){
                    continue;
                }
                queue.add(next);
                arr[next]=arr[point]+1;
                visit[next]=true;
            }
        }
    }
}

 

현위치 * 2이동을 구현하기 위해서 반복문의 i가 2면 next 값을 next*2로 바꿔준다.

 

모든 이동에 대해서 next값이 0미만 100000초과라면 이동을 하지 않는다.(주의 : 이하와 이상으로 하면 도착점이100000일 경우 방문을 못하므로 0이 출력된다.)

 

<전체 코드>

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

public class Problem1697 {

    static int[] arr = new int[100001];
    static boolean[] visit = new boolean[100001];
    static int[] move = {1,-1,2};

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int now = scanner.nextInt();;
        int point = scanner.nextInt();
        Arrays.fill(arr,0);
        BFS(now);

        System.out.println(arr[point]);
    }

    public static void BFS(int now){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(now);
        visit[now]=true;

        while(!queue.isEmpty()){
            int point = queue.poll();
            for(int i=0; i<3; i++){
                if(i==2){
                    int next = point*2;
                    if(next<0 || next>100000){
                        continue;
                    }
                    if(visit[next]){
                        continue;
                    }
                    queue.add(next);
                    arr[next]=arr[point]+1;
                    visit[next]=true;

                }
                else {
                    int next = point + move[i];
                    if(next<0 || next>100000){
                        continue;
                    }
                    if(visit[next]){
                        continue;
                    }
                    queue.add(next);
                    arr[next]=arr[point]+1;
                    visit[next]=true;
                }
            }
        }
    }
}