백준 1463 1로 만들기 자바

1로 만들기 문제 보러가기

1463번: 1로 만들기

문제 설명

자바 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;

public class Main {
    static int []isVisited;
    public static void main(String[] args) throws Exception{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(br.readLine());
        isVisited=new int[n+1];
        System.out.print(bfs(n));
    }

    static int bfs(int n){
        LinkedList<Integer> queue=new LinkedList<Integer>();
        queue.add(n);
        while (!queue.isEmpty()){
            int x=queue.peek();
            queue.poll();
            if(x==1) return isVisited[1];
            if(x%3==0){
                if(isVisited[x/3]==0)isVisited[x/3]=isVisited[x]+1;
                queue.add(x/3);
            }
            if(x%2==0){
                if(isVisited[x/2]==0)isVisited[x/2]=isVisited[x]+1;
                queue.add(x/2);
            }
            if(isVisited[x-1]==0)isVisited[x-1]=isVisited[x]+1;
            queue.add(x-1);

        }
        return isVisited[1];
    }

}

문제 풀이

이 문제는 bfs를 이용합니다. n 값을 2,3으로 나누거나 -1 합니다.

그리고 방문한 숫자를 배열로 만들어서 연산값을 넣습니다.

결과값은 isVisited[1]의 값을 출력하면 됩니다.