프로그래머스 : 숫자 변환하기 ( LV 2 )

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

프로그래머스

 

* 문제 딱 보자마자 bfs..? 풀수 있을거 같은데? 생각이 든 문제.

* 고민 끝에 bfs 알고리즘으로 풀었지만 예외처리를 안해줘서 틀렸다.

* 각 결과마다 +n, *2, *3을 한 값을 Queue에 넣어주면되는데, 예외처리로 y값을 넘기지 않는 선에서 넣어야한다.

* 끝이다. 코드로 구현하면 된다.

 

import java.io.*;
import java.util.*;

class Solution {
    int answer = 0;
    boolean[] visited;
    public int solution(int x, int y, int n) {
        answer = bfs(x, y, n);
        return answer;
    }
    private int bfs(int input, int output, int add) {
        Queue<Node> queue = new LinkedList<>();
        visited = new boolean[1000001];
        queue.add(new Node(input, 0));
        
        while(!queue.isEmpty()) {
            Node node = queue.poll();
            int curValue = node.value;
            int curCount = node.count;
            visited[curValue] = true;
            
            if(curValue == output) {
                return curCount;
            }
            
            if(output >= curValue+add && !visited[curValue+add]) {
                queue.add(new Node(curValue+add, curCount+1));
                visited[curValue+add] = true;
            }
            if(output >= curValue*2 && !visited[curValue*2]) {
                queue.add(new Node(curValue*2, curCount+1));
                visited[curValue*2] = true;
            }
            if(output >= curValue*3 && !visited[curValue*3]) {
                queue.add(new Node(curValue*3, curCount+1));
                visited[curValue*3] = true;
            }
        }
        return -1;
    }
}

class Node {
    int value, count;
    Node(int value, int count) {
        this.value = value;
        this.count = count;
    }
}

 

* visited 배열은 방문한 값에 한번더 방문하지 않기위한 방문배열이다.