[백준] 12851 숨바꼭질 2 Java

 

간단한 문제인데, 처리 부분에서 눈여겨 볼만한 부분이 있어서 포스팅한다. 골드4 문제이고 정답 비율은 약 26%로 낮은 편이다. 알고리즘 문제를 풀면서 느낀 건 티어보다도 정답 비율이 낮은 문제의 경우 세심한 처리를 요구하는 경우가 많다는 점이다. 코딩테스트에서 흔히 말하는 솔.. 을 하려면 주어지는 테스트케이스 이외에 모든 엣지 케이스에 대해서도 통과를 받아야 하기 때문에 이런 처리법 많이 연습해야만 한다 !!

 

 

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

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고, 가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 프로그램을 작성하시오.

 

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

 

출력

첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

둘째 줄에는 가장 빠른 시간으로 수빈이가 동생을 찾는 방법의 수를 출력한다.

가장 빠른 시간으로 수빈이가 동생을 찾는 방법의 수를 출력한다.

 

예제 입력

5 17

예제 출력

4
2

 

처음 이 문제를 보면 완전 탐색 알고리즘으로 풀어나갈 생각을 할 것이다. 나 또한 이 알고리즘을 어렵지 않게 떠올렸으며, 탐색 문제의 경우 재귀로 구현하는 DFS보다 BFS가 성능 상 이점이 있다고 배워서 BFS로 구현하고자 했다.

 

다만, 출력 제한에 적힌 한 문장이 걸렸다.

가장 빠른 시간으로 수빈이가 동생을 찾는 방법의 수를 출력한다.

 

가장 빠른 시간만을 출력한다면, BFS 탐색 후 너비 값을 출력하면 되는 문제로 정말 간단하다. 하지만, 가장 빠른 시간으로 찾는 방법의 '수'를 출력해야 했고, 이미 방문 처리된 정점이라고 해서 해당 케이스를 탐색 대상에서 무조건 배제할 수 없다는 뜻이었다.

 

우리에게 익숙한 일반적인 BFS에서는, 만약 다음으로 방문할 정점의 visited 배열 값이 true로 확인된다면 해당 정점을 큐 자료구조에 넣을 필요가 없지만 이 문제에서는 해당 정점이 큐 자료구조에 들어갈 수 있는 지를 확인해야 했다.

 

 

나는 메모리 사용량을 줄이기 위해, 시간 체크용 배열과 방문 여부 체크용 배열을 하나의 자료구조로 만들었다. visited 배열을 int[] 타입으로 선언하고, 'visited[n] 값이 0이면 n번 정점에 방문하지 않았다.'라고 판단하기로 했다. 또한, 'visited[n] 값이 4이면 n번 정점까지의 너비가 3이다, 즉 n번 정점까지 걸린 시간이 3초이다.'라고 판단하기로 했다.

 

Queue<Integer> q = new LinkedList<>();
q.offer(N);
visited[N] = 1;

 

실제 시간 값보다 1씩 큰 값이 들어가는 이유는, 출발 정점인 수빈이의 위치(N)에 대한 초기 방문 체크를 하기 위함이다.

 

if (cur - 1 >= 0) {
    if (visited[cur - 1] > 0) {
    	if (visited[cur] + 1 == visited[cur-1]) {
        	q.offer(cur-1);
        }
    } else {
        visited[cur-1] = visited[cur] + 1;
        q.offer(cur-1);
    }
}

 

 

일반적인 BFS 로직과 같게 현재 위치(cur)로부터 이동할 수 있는 정점 cur-1, cur+1, cur*2 로의 이동 가능 여부를 체크한다. 다만, 가장 빠른 시간이 소요되는 모든 케이스가 동생의 위치(K)까지 탐색할 수 있도록, 방문 처리 된 정점일지라도 현재 위치(cur)과 너비가 같은(같은 시간이 소요된) 정점에서 방문 처리된 경우라면 BFS 탐색을 이어나가도록 if 문을 구성했다.

 

정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class boj12851 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int res = 0;

        if (N == K) {
            System.out.println(0);
            System.out.println(1);
            return;
        }

        int[] visited = new int[100001];
        Queue<Integer> q = new LinkedList<>();
        q.offer(N);
        visited[N] = 1;

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

            if (cur == K) res++;

            if (cur - 1 >= 0) {
                if (visited[cur - 1] > 0) {
                    if (visited[cur] + 1 == visited[cur-1]) {
                        q.offer(cur-1);
                    }
                } else {
                    visited[cur-1] = visited[cur] + 1;
                    q.offer(cur-1);
                }
            }
            if (cur + 1 <= 100000) {
                if (visited[cur+1] > 0) {
                    if (visited[cur] + 1 == visited[cur+1]) {
                        q.offer(cur+1);
                    }
                } else {
                    visited[cur+1] = visited[cur] + 1;
                    q.offer(cur+1);
                }
            }
            if (cur * 2 <= 100000) {
                if (visited[cur*2] > 0) {
                    if (visited[cur] + 1 == visited[cur*2]) {
                        q.offer(cur*2);
                    }
                } else {
                    visited[cur*2] = visited[cur] + 1;
                    q.offer(cur*2);
                }
            }
        }

        System.out.println(visited[K]-1);
        System.out.println(res);

    }
}

 

 

이번 문제를 풀면서 느낀 건, 결국 구현력이 알고리즘 실력을 좌우하지 않나 싶다. 꾸준하게 많은 문제를 접하다보면 좋은 문제를 만나게 되고, 그게 코딩테스트에서의 좋은 결과로 이어지는 것 같다. 코테 고득점을 향해 화이팅해보자.