[백준] 1697번 - 숨바꼭질 (Java)

https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

 

<문제 분석>

1. 1차원 그래프이다.

2. N의 위치에서 할 수 있는 액션은 3개이다.

  2-1. nx = 2 * x

  2-2. nx = x+1

  2-3. nx = x - 1

3. BFS로 위 3개  액션을 for(1 to 3)문으로 돌려서 탐색한다.

4. 방문거리는 visited 배열에다가 이전거리+1을 해서 기록하고, 방문한 노드는 스킵한다.

5. N과 K가 같을 때 BFS 수행 전에 0을 출력해야하는 반례가 있음.(이것 때문에 계속 실패함!)

 

import java.util.*;

/*
[백준] 1697번 - 숨바꼭질 (Java)
*/

public class Main {
    int N, K;
    int visited[] = new int[100001];
    

    void InputData() {
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        K = in.nextInt();        
    }

    void BFS() {
        Queue<Integer> Q = new LinkedList<>();
        Q.offer(N);
        visited[N] = 1;
        
        while(!Q.isEmpty()) {
            int now = Q.poll();

            for (int i=0; i<3; i++) {
                int next;
                if (i == 0) {
                    next = now + 1;
                } else if (i == 1) {
                    next = now - 1;
                } else {
                    next = now * 2;
                }

                if (next == K) {
                    System.out.println(visited[now]);
                    return;
                }

                if (next < 0 || next > 100000) continue;
                if (visited[next] != 0) continue;

                Q.offer(next);
                visited[next] = visited[now] + 1;
            }
        }
    }

    int count = 0;
    void Solve() {
        if (N == K)
            System.out.println(0);// 반례
        else
            BFS();
    }
    
	public static void main(String[] args) {
		Main m = new Main();
        m.InputData();
        m.Solve();
	}
}

<제출 결과>

최단거리를 구할 때 습관적으로 자꾸 변수에다가 저장하려고 한다.

visited 배열을 활용하는 것이 더 효율적이다.