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

문제 링크

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

프로그래머스

 

 

---

💡 아이디어

x를 y로 변환하는 최소한의 연산 횟수를 구해야 하기 때문에 BFS로 풀어야겠다고 생각했습니다.

 

 

📗 풀이과정

1. BFS를 수행하기 위해 연산된 숫자와 연산 횟수를 저장할 수 있도록 Queue를 int [] 형으로 선언합니다.

import java.util.*;

Queue<int[]> q = new LinkedList<>();

 

2. x부터 연산이 시작되기 때문에 Queue에 x와 연산횟수0을 넣습니다.

q.add(new int[]{x,0});

 

3. 기존에 한 번 수행했던 연산을 다시 하지 않기 위해 visited배열을 선언합니다.

static boolean[] visited = new boolean[1000001]; // 1 <= x <= 1000000

 

4. while반복문에서 q가 비어있어있지 않을 때, 아래의 연산들을 수행합니다.

 

5. 현재 Queue의 맨 앞을 빼주고, 만약 그 수가 y인지 확인합니다. 만약 y라면 현재 연산 횟수를 cnt에 넣고 반복문을 나옵니다.

int[] now = q.poll();

if(now[0]==y){
	cnt=now[1];break; //연산횟수 cnt에 넣고 break
}

 

6. y가 아니라면, Queue에 현재 숫자(now [0])+n, now [0]*2, now [0]*3한 값을 연산 횟수+1 해서 넣어줍니다.

 

(* 여기서 주의해야할 점은 now [0]+n, now [0]*2, now [0]*3 이 y를 넘거나, 최소 연산 횟수를 구하는 것이므로 이미 연산했던 값이면 Queue에 넣지 않습니다.)

if(now[0]+n<=y && !visited[now[0]+n]){ //다음 숫자가 y보다 작거나 같고, 연산을 수행하지 않았으면
	q.add(new int[]{now[0]+n, now[1]+1});
	visited[now[0]+n]=true;
}
if(now[0]*2<=y && !visited[now[0]*2]){
	q.add(new int[]{now[0]*2,now[1]+1});
	visited[now[0]*2]=true;
}
if(now[0]*3<=y && !visited[now[0]*3]){
	q.add(new int[]{now[0]*3, now[1]+1});
	visited[now[0]*3]=true;
}

 

7. 만약 반복문이 종료될 때까지 y로 변환할 수 없다면 초기 선언값인 -1을 return 합니다.

 

---

전체 코드

import java.util.*;
class Solution {
    static boolean[] visited = new boolean[1000001];
    public int solution(int x, int y, int n) {
        
        return bfs(x,y,n);
    }
    //너비 우선 탐색 bfs
    int bfs(int x, int y, int n){
        
        int cnt=-1;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{x,0});
        
        while(!q.isEmpty()){
            int[] now = q.poll();
            if(now[0]==y){
                cnt = now[1];break;
            }
            
            if(now[0]+n<=y && !visited[now[0]+n]){
                q.add(new int[]{now[0]+n, now[1]+1});
                visited[now[0]+n]=true;
            }
            if(now[0]*2<=y && !visited[now[0]*2]){
                q.add(new int[]{now[0]*2,now[1]+1});
                visited[now[0]*2]=true;
            }
            if(now[0]*3<=y && !visited[now[0]*3]){
                q.add(new int[]{now[0]*3, now[1]+1});
                visited[now[0]*3]=true;
            }
        }
        
        return cnt;
    }
}