[프로그래머스] 숫자 변환하기

코드 힌트

1. 목표:
   • 주어진 숫자 x에서 시작해 목표 숫자 y에 도달하는 최소 연산 횟수를 구합니다.
   • 사용 가능한 연산은 n을 더하기, 2를 곱하기, 3을 곱하기입니다.
2. BFS (너비 우선 탐색):
   • BFS를 사용해 최단 경로를 찾습니다.
   • BFS는 주어진 상태에서 가능한 모든 다음 상태를 큐에 추가하고, 하나씩 처리하면서 목표 상태에 도달하는지를 확인합니다.
3. 방문 체크:
   • 아마 대부분의 사람들이 시간초과의 이유로 찾으셨을거라고 생각합니다.
   • 이미 방문한 숫자는 최소 횟수가 아니므로 visit 배열을 사용하여 이미 방문한 숫자는 다시 방문하지 않도록 visited 배열을 사용합니다.
4. 종료 조건:
   • 목표 숫자 y에 도달하면 그때까지의 연산 횟수를 반환합니다.
   • 큐가 비었음에도 목표에 도달하지 못했다면 -1을 반환해 불가능함을 나타냅니다.

 

 

---

정답은 더보기 클릭

import java.util.*;

class Solution {
    public int solution(int x, int y, int n) {
        // BFS를 이용하여 x에서 y로 가는 최소 연산 횟수를 찾음
        return bfs(x, y, n);
    }
    
    int bfs(int x, int y, int n) {
        // BFS 탐색을 위한 큐, 초기 상태는 {x, 0} (현재 숫자, 연산 횟수)
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{x, 0});
        
        // 방문 체크 배열, 숫자 y까지 방문 여부를 기록
        boolean[] visited = new boolean[y+1];
        
        while (!q.isEmpty()) {
            int[] tmpArr = q.poll(); // 현재 상태를 큐에서 꺼냄
            int currNum = tmpArr[0]; // 현재 숫자
            int count = tmpArr[1];   // 연산 횟수
            
            // 현재 숫자가 목표 숫자 y와 같다면, 연산 횟수를 반환
            if (currNum == y) return count;
            
            // 가능한 연산을 통해 새로운 숫자를 계산하고 큐에 추가
            if (currNum + n <= y && !visited[currNum+n]) {
                q.add(new int[] {currNum+n, count+1});
                visited[currNum+n] = true; // 방문 체크
            }
            if (currNum * 2 <= y && !visited[currNum*2]) {
                q.add(new int[] {currNum*2, count+1});
                visited[currNum*2] = true; // 방문 체크
            }
            if (currNum * 3 <= y && !visited[currNum*3]) {
                q.add(new int[] {currNum*3, count+1});
                visited[currNum*3] = true; // 방문 체크
            }
        }
        
        // 큐가 비었는데도 목표 숫자 y에 도달하지 못한 경우 -1 반환
        return -1;
    }
}