[JAVA] 백준 12851번: 숨바꼭질 2

🔗 문제

12851번: 숨바꼭질 2

12851번: 숨바꼭질 2

이 문제는 전에 풀었던 숨바꼭질, 이모티콘이랑 유사하다.

다른 점이 있다면 최소 연산 횟수 뿐만 아니라 이 조건을 만족하는 ‘경우의 수’도 포함하여 출력해야 한다.

 

✏️ 풀이

 

기본접근법은 소개했던 문제들은 특정 알고리즘을 떠올려야 하는게 키 포인트였다면,

이 문제는 더 나아가 경우의 수를 어떻게 포함할지 고민하는게 포인트다.

 

 

((스포))

 

 

이 문제는 BFS로 풀어야 하며, queue에 있던 원소를 꺼낼 때 방문 처리를 해주어야 한다.

 

[접근법]

처음에는 DFS로 풀려고 했는데, DFS 특성상 함수에 가장 먼저 정의된 연산만 계속해서 파고 든다.

이렇게 되면 택도 없는걸 계속해서 파고 들기 때문에 안된다.

 

❓ 왜 BFS를 써야 하는가?

BFS가 어떤 상태에서 공평하게 (?) 기회를 나눠주기 때문에 이 문제에 적합하기 때문이다.

 

 

 

>> 최소 연산 횟수 구하기

우리가 구하고자 하는 것은 필요한 최소 연산 횟수다.

특정 상태 (현재 이동한 위치)에서 공평하게 3가지 연산을 다 해보고 그 값이 K인지 확인을 해야한다.

가장 처음 K를 만족한 값이 우리가 출력해야할 ‘최소 연산 횟수’가 된다.

 

 

 

>> 경우의 수 구하기

 

나이브하게 접근하다가 메모리초과를 보았다.

 

직접 트리를 그려보면 쉽게 이해할 수 있다. 한 레벨마다 pop한 노드를 루트로 두고 어떤 노드가 아래에 달리는지 그려보자. 레벨 3부터 중복되는 루트 X, 자식 노드O들이 있는데 여기서 생각을 잘 해야한다.

 

아직 한 레벨에 어떤 노드들이 달릴지 모두 알지 못 했는데 방문 체크를 해버린다면?

그 중복된 노드가 만약 우리가 찾는 K라면 영원히 K는 단 한 번만 카운트 된다.

그래서 queue를 꺼낼 때 방문체크를 해주고 넣을 때 중복으로 넣지 않도록 해주었다.

 

 

 

오답 코드

while(!q.isEmpty())
{
    if(cnt != 0)
    {
        System.out.printf("%d\\n%d", depth, cnt);
        return;
    }
    
    ++depth;

    int qSize = q.size();
    while(qSize-- > 0)
    {

        e = q.poll();
        
        for(int i=0; i<3; ++i)
        {
            if(i==0) x = e + 1;
            else if(i ==1) x = e - 1;
            else if(i==2) x = e *2;
            
            if(x == k) ++cnt;

            if(x < 0 || x >= MAX_SIZE  || visited[x]) continue;
            visited[e] = true; // 여기서 해버리면 X
            q.offer(x);
        }

    }
}

 

 

정답 코드

while(!q.isEmpty())
{
    if(cnt != 0)
    {
        System.out.printf("%d\\n%d", depth, cnt);
        return;
    }
    ++depth;

    int qSize = q.size();
    while(qSize-- > 0)
    {
        e = q.poll();
        visited[e] = true; // 저장된 값을 꺼낼 때만 확인한다. 

        for(int i=0; i<3; ++i)
        {
            if(i==0) x = e + 1;
            else if(i ==1) x = e - 1;
            else if(i==2) x = e *2;
            
            if(x == k) ++cnt;

            if(x < 0 || x >= MAX_SIZE  || visited[x]) continue;
            q.offer(x);
        }

    }
}

 

 

💾  소스

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

public class Main {
    static BufferedReader br  = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    final static int MAX_SIZE = 100000+1;

    static void solve(final int n, final int k) {

        if(n == k) // 둘이 같을 때는 예외 처리로 넣어줌
        {
            System.out.printf("0\\n1");
            return;
        }
        
        int depth = 0, cnt = 0;

        Queue<Integer> q = new ArrayDeque<>();
        q.offer(n);

        boolean[] visited = new boolean[MAX_SIZE];
        visited[n] = true;

        int e, x = 0;
        while(!q.isEmpty())
        {
            if(cnt != 0) // 다음 레벨로 진행하는데 이미 최소 연산 횟수를 찾았으니 중단!
            {
                System.out.printf("%d\\n%d", depth, cnt);
                return;
            }
            ++depth;

            int qSize = q.size();
            while(qSize-- > 0)
            {

                e = q.poll();
                visited[e] = true; // 넣은 값을 꺼낼 때 방문 처리한다 

                for(int i=0; i<3; ++i)
                {
                    if(i==0) x = e + 1;
                    else if(i ==1) x = e - 1;
                    else if(i==2) x = e *2;
                    
                    if(x == k) ++cnt;

                    if(x < 0 || x >= MAX_SIZE  || visited[x]) continue;
                    q.offer(x);
                }

            }
        }
    }

    public static void main(String[] args) throws IOException {

        st = new StringTokenizer(br.readLine());
        solve(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
    }
}