[백준] code.plus(BFS 알고리즘,JAVA)14395번, 4연산

문제 링크

14395번: 4연산

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

 

접근 방법

그래프 알고리즘이란?

각 정점과 연결하는 선분의 정보를 가지고 BFS(너비 우선 탐색), DFS(깊이 우선 탐색) .... 등을 이용하여 정점에서 다른 정점으로 가는 최소값, 최대값 등의 문제에서 출력하라는 결과를 구하는 알고리즘입니다.

 

BFS?

BFS(너비 우선 탐색)은 아래 그림처럼 시작 노드에 인접한 노드를 모두 탐색한 후 인접한 노드를 기준으로 다시 인접한 노드를 찾아내는 것을 반복하여 탐색합니다.

시작 노드 탐색이 끝나면 인접했던 노드를 시작 노드로 생각하고 다시 탐색합니다.

출처: https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

더 자세한 내용은 아래 링크에 들어가서 확인해주시면 감사하겠습니다.

너비 우선 탐색 - 위키백과, 우리 모두의 백과사전

 

이 문제에 핵심은

1. 사칙연산을 진행하여 s의 값이 t가 되는 최소 연산횟수를 결과로 출력합니다.

2. 사칙연산은 자기 스스로의 값끼리 연산됩니다.

3. 가능한 방법이 여러가지인 경우 사전 순으로 앞서는 형태로 출력합니다.

 

사칙연산을 진행할 때

나누기와 빼기의 값은 항상 같습니다.

나누기 : s ÷ s = 1

빼기 : s - s = 0

 

 

BFS탐색을 통해서 s의 값에 대해서 사칙연산을 진행하여 가장 먼저 t에 도착하는 연산자들을 결과로 출력하였습니다.

 

 

예제입력 3.

 

s = 4, t = 256

 

BFS 탐색 시작!

 

곱하기

 

4 * 4 = 16

 

더하기

 

4 + 4 = 8

※나누기와 뺄셈은 항상 값이 같기 때문에 한 번만 사용합니다!

빼기

 

4 - 4 = 0

 

나누기

 

4 / 4 = 1

 

다음 탐색시작!

 

s = 16, 8, 0, 1 t = 256

 

곱하기

16 * 16 = 256

 

가장 먼저 목적값에 도달하였기 때문에 해당 연산(**)을 결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer을 이용하여 s와 t를 저장하였습니다.
• s가 t에 도달하는지 사칙연산을 BFS탐색하는 bfs함수를 실행하였습니다.
• t에 도달시 최소 연산자, 도달 못할 때 -1을 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• bfs는 s가 t에 도달하는 최소 연산자를 구하기 위해 BFS탐색하는 함수입니다.
• bfs함수는 t에 도달하면 최소 연산자, 도달하지 못하면 -1을 반환합니다.

 

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

public class Main {
	//BFS Queue에 사용되는 클래스
    static class num{
        int num;
        String operator;
        public num(int num, String operator) {
            this.num = num;
            this.operator = operator;
        }
    }
    static int S,T;
    static int max = 1000000000;	//나올 수 있는 최대값
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //입력값 출력하는 BufferedWriter
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        S = Integer.parseInt(st.nextToken());
        T = Integer.parseInt(st.nextToken());
        if(S==T)		//s와 t가 같을 때
            bw.write("0");
        else		//s와 t가 같지 않을 때
            bw.write(bfs() + "");
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //사칙연산을 진행하여 s가 t가 되는 최소 연산을 BFS탐색하는 함수
    static String bfs(){
        Queue<num> queue = new LinkedList<>();
        boolean[] visited = new boolean[max+1];
        boolean first  = false;
        visited[S] = true;
        queue.add(new num(S,""));
        //탐색시 아스키 코드 순으로 *+-/으로 진행됩니다.
        while(!queue.isEmpty()){
            num cur = queue.poll();
            int num = cur.num;
            String operator = cur.operator;
            if(num==T)		//목표 t에 달성
                return operator;
            //곱하기
            long temp1 = (long)num * num;
            if(temp1<=max && !visited[(int)temp1]){
                visited[(int)temp1] = true;
                queue.add(new num((int)temp1,operator+"*"));
            }
            //더하기
            int temp2 = num+num;
            if(temp2<=max && !visited[temp2]){
                visited[temp2] = true;
                queue.add(new num(temp2, operator+"+"));
            }
            //항상 값이 같은 빼기와 나누기는 첫 탐색에만 실행
            if(!first){
                first = true;
                visited[0] = true;
                visited[1] = true;
                queue.add(new num(0, operator+"-"));	//나누기
                queue.add(new num(1, operator+"/"));	//빼기
            }
        }

        return "-1";	//t까지 도달 불가능시
    }
}