백준 1697 숨바꼭질 JAVA

solved.ac = 실버 1

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

1697번: 숨바꼭질

 

1. 접근

 

N과 K모두 최대 10만에 있을 수 있고 방문횟수 또한 끝에서 끝 지점으로 -1로만 이동했을 경우 10만번 방문한다. 즉 시간복잡도 및 최대값은 10만으로 BFS로 접근 가능하다.

 

BFS 문제이지만 노골적으로 격자판이나 그래프가 주어지지 않기 때문에 수빈이의 위치와 동생의 위치까지를 각 정점으로 볼 수 있고 이동 가능한 경로는 그림과 같이 x - 1, x + 1, x * 2이며 가중치는 모두 1로 볼 수 있다.

문제에선 동생을 찾기위한 최단거리를 묻고 있으니 각 정점마다 방문 가능한 세 곳을 방문하고 기록하며 가다가 동생의 위치가 방문처리 되면 break 후 출력하면 된다.

 

2. 풀이

 

전역변수 및 input

static int N, K;
static int[] dist;
public static void main(String[] args) throws IOException {
    st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken()); // 수빈이의 위치
    K = Integer.parseInt(st.nextToken()); // 동생의 위치
    dist = new int[100001]; // 입력 최대값
    solution();
}

 

배열 초기화 및 BFS 호출

static void solution() {
    Arrays.fill(dist, -1); // 방문여부 및 카운트 체크용
    BFS();
    System.out.println(dist[K]);
}

 

BFS

static void BFS() {
    Queue<Integer> Q = new LinkedList<>();
    Q.add(N); // 수빈이의 위치부터 시작한다.
    dist[N] = 0; // 방문처리

    while(!Q.isEmpty()) {
        if(dist[K] != -1) break; // 동생을 잡았다!
        int x = Q.poll();
        if (x - 1 >= 0 && dist[x - 1] == -1) { // -1 했을 경우
            Q.add(x - 1);
            dist[x - 1] = dist[x] + 1;
        }
        if (x + 1 <= 100000 && dist[x + 1] == -1) { // +1 했을 경우
            Q.add(x + 1);
            dist[x + 1] = dist[x] + 1;
        }
        if (x * 2 <= 100000 && dist[x * 2] == -1) { // *2 했을 경우
            Q.add(x * 2);
            dist[x * 2] = dist[x] + 1;
        }
    }
}

 

3. 전체코드