백준 13549 (숨바꼭질3) java

문제

입력

import java.util.*;
import java.io.*;
class Main {

    static int n = 0;
    static int m = 0;
    static int[] visit = new int[100001];
    static int result = -1;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] line = bf.readLine().split(" ");
        n = Integer.parseInt(line[0]);
        m = Integer.parseInt(line[1]);

        visit[n]=1;

        bfs(n);

        System.out.println(visit[m]-1);
        bf.close();
    }

    static void bfs(int x) // 수빈이의 시작 위치부터 시작
    {
        Queue<Integer> q= new LinkedList<>();
        q.add(x);

        while(!q.isEmpty()) {
            int cur = q.poll();

            for (int i = 1; i <= 3; i++) {
                int nx=0;

                if (i == 1) {
                    nx = cur + 2;
                }

                if(i==2)
                {
                    nx = cur - 1;
                }

                if(i==3)
                {
                    nx = cur * 2;
                }

                if(nx>=0&&nx<=100000)
                {
                    if(visit[nx]==0||visit[nx]>=visit[cur]+1) // !!!!
                    {
                        if(i==3) // 순간이동의 경우
                        {
                            visit[nx]=visit[cur];
                            q.add(nx);
                        }
                        else{ 
                            visit[nx]=visit[cur]+1;
                            q.add(nx);
                        } // 그냥 좌표 이동의 경우
                    }
                    else if(nx==m) // 동생을 찾았을 때
                    {
                        if(i==3) // 순간이동해서 찾은 경우
                        {
                            if(visit[m]==0||visit[m]>=visit[cur])
                                visit[m] =visit[cur];
                        }
                        else{
                            if(visit[m]==0||visit[m]>=visit[cur]+1)
                                visit[m] =visit[cur] + 1;
                        } // 이동으로 찾은 경우
                    }
                }

            }
        }
    }

}

 

방문처리하고 큐에 추가하는 조건식이다. 이 문제에서 중요한 점은 방문하지 않은 경우에만 처리하는 것이 아니라 순간이동이라는 변수에 대한 처리도 해줘야 하는 것이다. 기존에 방문했던 위치이더라도 더 빠르게 도착할 수 있기 때문에 해당 경우에 대해서도 고려해줘야 한다.

 

그리고 먼저 동생을 찾았더라도 더 적은 수의 이동으로 동생을 찾을 수 있기 때문에 바로 종료하지 않고 나머지 경우에 대해서도 계산을 해줘야 한다.