문제

BOJ 14395: 4연산 https://www.acmicpc.net/problem/14395

풀이

조건

• 정수 s의 값을 t로 바꾸는 최소 연산 횟수를 구한다.
  • 이 때 연산 과정을 출력한다.
• 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다.
  1. s = s + s; (출력: +)
  2. s = s - s; (출력: -)
  3. s = s * s; (출력: *)
  4. s = s / s; (출력: /) (s가 0이 아닐때만 사용 가능)
• s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다.

풀이 순서

• BFS를 사용하여 해결한다.
• Num 구조체를 만든다.
  • Num 객체에 해당 숫자인 num과 num까지 해왔던 연산을 저장할 history를 넣는다.
• Set을 사용하여 연산한 숫자가 중복되지 않도록 한다.

코드

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

public class Main {  
	
	static long s, t;

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		s = Long.parseLong(st.nextToken()); // 시작 숫자
		t = Long.parseLong(st.nextToken()); // 목표 숫자
		
		bfs(s, t);
	}
	
	static void bfs(long start, long target) {
		// 아스키 코드 순서대로 배열 생성
		String[] order = new String[] {"*", "+", "-", "/"};
		// 중복 체크할 Set
		HashSet<Long> set = new HashSet<>();
		
		// s와 t가 같으면 0 출력
		if(start == target) {
			System.out.println(0);
			return;
		}
		
		Queue<Num> que = new LinkedList<>();
		set.add(start);
		que.add(new Num(start, ""));
		
		while(!que.isEmpty()) {
			Num now = que.poll();
			
			long nowNum = now.num;
			String nowHistory = now.hisory;
			
			long next = nowNum; // 연산 후의 숫자
			
			// 목표 숫자에 도달하면 현재까지 해왔던 연산 출력
			if(nowNum == target) {
				System.out.println(nowHistory);
				return;
			}
			
			// 아스키 코드 순서대로 연산
			for(int t=0; t<4; t++) {
				switch(t) {
					case 0:
						next = nowNum * nowNum;
						break;
					case 1:
						next = nowNum + nowNum;
						break;
					case 2:
						next = nowNum - nowNum;
						break;
					case 3:
						if(nowNum != 0) {
							next = nowNum / nowNum;
						}
						break;
				}
				// 중복된 숫자가 아니면
				if(!set.contains(next)) {
					// Set과 Queue에 삽입 
					set.add(next);
					que.add(new Num(next, nowHistory + order[t]));
				}
			}
		}
		
		// 바꿀 수 없는 경우 -1 출력
		System.out.println(-1);
		return;
	}
	
	static class Num {
		// 숫자
		long num;
		// 해당 숫자까지 해왔던 연산을 저장할 변수
		String hisory = "";
		
		Num(long num, String history){
			this.num = num;
			this.hisory = history;
		}
	}
}  

정리

• 숫자의 중복 체크를 사용할 때 Set을 사용했다.
• 연산한 과정을 객체에 담아 저장하는 방법을 알았다.
• 4방 탐색이 아닌 BFS문제를 연습해야겠다.