백준 - 1697 - 숨바꼭질

www.acmicpc.net/problem/1697

1697번: 숨바꼭질

 

import java.util.*;
 
/**
 * 백준 - 1697
 */
public class 숨바꼭질 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] inputs = sc.nextLine().split(" ");
        Integer N = Integer.valueOf(inputs[0]);
        Integer K = Integer.valueOf(inputs[1]);
 
        System.out.println(bfs(N, K));
    }
 
    private static int bfs(Integer N, Integer K) {
        Queue<Integer> q = new LinkedList<>();
        int[] dist = new int[100001];
        Arrays.fill(dist, -1);
 
        q.offer(N);
        dist[N] = 0;
 
        while (!q.isEmpty()) {
            Integer curNode = q.poll();
 
            int[] nextPos = new int[]{curNode-1, curNode+1, curNode*2};
            for(int i=0; i<nextPos.length; i++) {
                Integer nextNode = nextPos[i];
                if(0 <= nextNode && nextNode <= 100000 && dist[nextNode] == -1) {
                    q.offer(nextNode);
                    dist[nextNode] = dist[curNode] + 1;
 
                    if(nextNode == K) {
                        q.clear();
                        break;
                    }
                }
            }
        }
 
        return dist[K];
    }
}
 

알고리즘

• BFS
• DFS를 사용할 경우, 완전 탐색하면서 최단거리를 계속 체크해줘야하는 단점이 있다. BFS를 이용할 경우 시작 노드로부터 가까운 노드부터 방문하기 때문에 그냥 처음 방문된 목적 노드가 가장 거리가 짧은 노드가 돼서, 목적 노드 방문시 로직을 종료할 수 있다.
• 방문 체크는 따로 메모리 할당을 하지 않고 최단거리배열(dist)의 수정 여부로 체크하였다.