[프로그래머스/Lv.2] 숫자 변환하기 (Java)

숫자 변환하기 

https://school.programmers.co.kr/learn/courses/30/lessons/154538

---

풀이

BFS

• `Queue<Integer> q = new ArrayDeque<>()`
• `int[] dist = new int[y + 1]`
  • `dist[v]`: v에 도착하기까지의 최소 연산 횟수
  • `Arrays.fill(dist, -1)`: 방문 X로 초기화

 

가능한 3가지 연산

• x에 n 더하기: `cur + n`
• x에 2 곱하기: `cur * 2`
• x에 3 곱하기: `cur * 3`

-> y 넘어가면 의미 X + 방문 안 한 경우(-1)만 탐색

if (cur + n <= y && dist[cur + n] == -1) {
    dist[cur + n] = dist[cur] + 1;
    q.add(cur + n);
}

if (cur * 2 <= y && dist[cur * 2] == -1) {
    dist[cur * 2] = dist[cur] + 1;
    q.add(cur * 2);
}

if (cur * 3 <= y && dist[cur * 3] == -1) {
    dist[cur * 3] = dist[cur] + 1;
    q.add(cur * 3);
}

---

코드

import java.util.*;

class Solution {
    public int solution(int x, int y, int n) {
        Queue<Integer> q = new ArrayDeque<>();
        int[] dist = new int[y + 1];
        Arrays.fill(dist, -1);
        
        q.add(x);
        dist[x] = 0;
        
        while (!q.isEmpty()) {
            int cur = q.poll();
            
            if (cur == y) return dist[cur];
            
            if (cur + n <= y && dist[cur + n] == -1) {
                dist[cur + n] = dist[cur] + 1;
                q.add(cur + n);
            }
            
            if (cur * 2 <= y && dist[cur * 2] == -1) {
                dist[cur * 2] = dist[cur] + 1;
                q.add(cur * 2);
            }

            if (cur * 3 <= y && dist[cur * 3] == -1) {
                dist[cur * 3] = dist[cur] + 1;
                q.add(cur * 3);
            }
        }
        return -1;
    }
}