[프로그래머스] 숫자 변환하기 자바 (Level 2) BFS

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/154538

1. 문제 요약

• x를 y로 변환하기까지 소요되는 최소 연산횟수 구하기
• 불가능할 경우 -1
• 연산은 x * 2 , x * 3, x + n 3가지 연산을 사용한다.

2. 핵심 아이디어

• BFS방식 . y까지 가는 가장 짧은 경로
• Queue에 (값, 연산횟수) 저장
• 3가지 연산을 수행해 큐에 추가
• y를 만나면 그때의 연산횟수 리턴 (y 조우 연산횟수 == 최소 연산횟수)
• 방문체크(visited) 를 해서 같은 값을 중복 방문하지 않게 한다

3. 풀이 코드

public int solution(int x, int y, int n) {
        Queue<int[]> queue = new LinkedList<>();
        boolean[] visited = new boolean[y + 1]; //최대 y.
        queue.offer(new int[]{x, 0}); // x와 소요횟수
        visited[x] = true;

        while(!queue.isEmpty()){
            int[] now = queue.poll();
            int v = now[0], cnt = now[1];

            if(v == y) return cnt;

            //3가지 연산
            if(v + n <= y && !visited[v + n]){
                visited[v + n] = true;
                queue.offer(new int[]{v + n, cnt + 1});
            }
            if(v * 2 <= y && !visited[v * 2]){
                visited[v * 2] = true;
                queue.offer(new int[]{v * 2, cnt + 1});
            }
            if(v * 3 <= y && !visited[v * 3]){
                visited[v * 3] = true;
                queue.offer(new int[]{v * 3, cnt + 1});
            }
        }

        return -1;
    }

4. 회고 및 느낀점

• BFS방식에 익숙해졌다고 생각했지만 새로운 유형을 만나면 응용이 원활하지 않았다.