[백준 13549] 숨바꼭질 3

생각 정리

현재 위치 X에서 할 수 있는 일
1. 1초 후, X-1 또는 X+1 로 이동
2. 0초 후, 순간이동
세 가지 경우를 고려하면서 순간이동할때만 시간 안더해주면 되지 않을까 ?
배열의 크기는 수빈이의 현재위치 * 2 +1로 정해둔다.

생각하지 못한 것

1. X-1 또는 X+1 이동과 순간이동의 가중치를 다르게 처리해주어야 한다는 것 (0-1 BFS 알고리즘이라고 한다.)
   • 순간이동하는 경우 queue의 맨 앞에 넣는다.
2. 수빈이의 위치와 동생의 위치를 비교할 때는 탐색하는 위치 (-1, +1 x2)가 아니라 현 위치로 비교해야 한다.
3. 탐색할 때, x2, -1, 1 순서로 탐색한다. (-1, 1 순서와 1, -1의 순서일 때 결과값 (가장 빠른 시간)이 달랐다. )
   • 탐색을 처음으로 할때만 시간을 업데이트 했기 때문인듯 !
   • 더 빨리 도착하는 방법이 나오면 다시 갱신 했음

코드

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

public class Main{
    static int N, K;
    static boolean[] visited;
    static int[] dist;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken()); // 수빈이의 현재위치
        K = Integer.parseInt(st.nextToken()); // 동생의 현재위치

        visited = new boolean[200001];
        dist = new int[100001];
        
        bfs(N);
        //bfs2(N);
    }

    static void bfs(int curr) {
        LinkedList<Integer> queue = new LinkedList<>();
        queue.add(curr);
        visited[curr] = true;
        int min = Integer.MAX_VALUE;

        while(!queue.isEmpty()) {
            int out = queue.poll();

            if(out == K){
                System.out.println(dist[out]);
                return ;
            }

            int[] move = {out, -1, 1};
            
            for(int i=0; i<3; i++) {
                int next = out + move[i];

                if(next < 0 || next > 100000) continue;
                else if(visited[next]) continue;
                else {
                    if(i != 0) { //순간이동하는 경우 아니면
                        queue.offer(next);
                        visited[next] = true;
                        dist[next] = dist[out] + 1;
                      
                    }
                    else { 
                        queue.addFirst(next);
                        visited[next] = true;
                        dist[next] = dist[out];
                       
                    }
                    
                }
            }
        }

        return ;
    }
}

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

public class Main {
    static int N, K;
    static boolean[] visited;
    static int[] dist;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken()); // 수빈이의 현재위치
        K = Integer.parseInt(st.nextToken()); // 동생의 현재위치

        visited = new boolean[100001];
        dist = new int[100001];


        bfs(N);
    }

    static void bfs(int curr) {
        LinkedList<Integer> queue = new LinkedList<>();
        queue.add(curr);
        visited[curr] = true;
        int min = Integer.MAX_VALUE;

        while(!queue.isEmpty()) {
            int out = queue.poll();
           // visited[out] = true;

            if(out == K){
                System.out.println(dist[out]);
                return ;
            }

            int[] move = {out,  1, -1};
            for(int i=0; i<3; i++) {
                int next = out + move[i];

                if(next < 0 || next > 100000) continue;
                else if( visited[next]) continue;
                else {
                    if(i != 0) { //순간이동하는 경우 아니면
                        queue.offer(next);
                        visited[next] = true;
                        if(dist[next] != 0)
                            dist[next] = Math.min(dist[next], dist[out]+1);
                        else
                            dist[next] = dist[out] + 1;
                    }
                    else { 
                        queue.addFirst(next);
                        
                        visited[next] = true;
                        if(dist[next] != 0)
                            dist[next] = Math.min(dist[next], dist[out]);
                        else
                            dist[next] = dist[out];
                    }
                }

            }
        }

        return ;
    }
}