숨바꼭질

풀이

 처음에는 -, +, * 연산 중에서 최선으로 * 연산을 수행하고 차선으로 + 연산을 수행해야 하는 그리디 유형의 문제라 생각했다. 하지만 계속 틀렸다... 단순히 그리디가 아니라 경우에 따라서는 - 연산을 수행해야 하는 경우도 있었다. 따라서 -, +, * 세 연산을 모두 탐색하면서 K에 도달하면 값을 반환하는 BFS로 접근을 바꿔서 풀 수 있었다.

시간 복잡도 : O(N)
💡 Java 풀이입니다. Python 풀이와 다를 수 있습니다.

Java

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static int N,K;
    static int[] visited;

    public static int BFS(){
        Queue<Integer> queue = new LinkedList<>();
        visited = new int[100001];
        queue.offer(N);
        while (!queue.isEmpty()){
            Integer tem = queue.poll();
            if(tem==K){
                return visited[tem];
            }
            if(tem-1>=0 && visited[tem-1]==0){
                visited[tem-1]= visited[tem]+1;
                queue.offer(tem-1);
            }
            if (tem+1<=100000 && visited[tem+1]==0) {
                visited[tem+1] = visited[tem]+1;
                queue.offer(tem+1);
            }
            if (tem*2<=100000 && visited[tem*2]==0) {
                visited[tem*2] = visited[tem]+1;
                queue.offer(tem*2);
            }
        }
        return -1;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        int result = BFS();

        bw.write(String.valueOf(result));
        bw.flush();
        bw.close();
        br.close();
    }
}

Python

from collections import deque
N, K = map(int, input().split())
visited = [-1] * 200001

queue = deque([N])
visited[N] = 0
while queue:
    x = queue.popleft()
    if x == K:
        print(visited[x])
        break
    if 0 <= x-1 < 200000:
        if visited[x-1] == -1:
            visited[x-1] = visited[x] + 1
            queue.append(x-1)
    if 0 <= x + 1 <= 200000:
        if visited[x+1] == -1:
            visited[x+1] = visited[x] + 1
            queue.append(x+1)
    if 0 <= x * 2 <= 200000:
        if visited[x*2] == -1:
            visited[x*2] = visited[x] + 1
            queue.append(x*2)