[알고리즘] 프로그래머스 - 숫자변환하기 (BFS, Java)

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

package Programmers;

import java.util.LinkedList;
import java.util.Queue;

public class 숫자변환하기 {
    static int globalX, globalY, globalN;

    static int tempAnswer = -1;
    static int[] chMap; //들렸던길 체크
    static Queue<Integer> q = new LinkedList<>();

    public static void main(String[] args){
        int x = 10; //시작지점
        int y = 40; //도착지점
        int n = 5; //변수
        숫자변환하기 T = new 숫자변환하기();
        T.solution(x, y, n);

    }

    public int solution(int x, int y, int n) {
        int answer = 0;
        chMap = new int[1000001];
        globalX = x;
        globalY = y;
        globalN = n;
        //x + n , x * 2, x * 3
        chMap[x] = 1;
        q.offer(x);
        bfs(x);



        return answer = tempAnswer;
    }


    public void bfs(int s){
        int L = 0;
        while (!q.isEmpty()){
            int qsize = q.size();
            for (int i = 0; i < qsize; i++) {
                int t = q.poll();
                if(t == globalY) tempAnswer = L;
                for (int j = 0; j < 3; j++) {//for돌면서 Calc 에다가 넣는다.
                    int nextS = Calc(t, j);
                    if(nextS  <= globalY && chMap[nextS] == 0){
                        chMap[nextS] = 1;
                        q.offer(nextS);
                    }
                }
            }
            L++;
        }
    }
    public int Calc(int s, int i){
        if(i == 0){
            return s+globalN;
        } else if (i == 1) {
            return s*2;
        }else{
            return s*3;
        }
    }



}

1. BFS탐색으로 품

2. Calc 메서드는 조건수행할 메서드 (n더하고 2곱하고 3곱하고)

3. bfs 메서드 - 시작점 입력받아서 q가 빌때까지 돈다.

3. bfs 메서드 - 처음 q사이즈를 기록해서 Que 뽑기전에 레벨을 체크한다.

4. bfs 메서드 - q에서 뽑아서 목표값에 도달했는지 확인하고 현재의 레벨 L 값을 tempAnswer 에다가 집어넣는다 

(메서드를 따로 뽑아서 그냥 전역으로 tempAnswer 하나 만듬 이후에 answer에다가 값 대입)

5. for 문 0, 1, 2 돌면서 n더하고, 2곱하고, 3곱하고 Calc 메서드에 넣어서 값 돌려받는다.

6. 목표값이랑 같거나 작으면 && 방문안했으면 chMap에 왔던길 표시하고 que에 추가한다. 

 

 

※ 처음에 nextS < globalY 로 목표값이랑 같을때 추가를 안해줘서 해맴

if(nextS  <= globalY && chMap[nextS] == 0){