[백준] G5 14395 4연산 (java)

www.acmicpc.net/problem/14395

14395번: 4연산

 

 

풀이

 

1) bfs를 돌림

1-1)  나오는 애들을 4연산을 하여 queue에 연산된 숫자, 누적된 연산자를 저장

1-2) queue.poll().num이 t가 되면 누적된 연산자를 출력후에 리턴.

 

주의사항

 

1) 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다. 연산의 아스키 코드 순서는 '*', '+', '-', '/' 이다.

• 이 말은 즉 dir[]을 *, +, - / 순서로 만들라는 뜻이다.

2) 최소 연산 횟수이므로 dfs가 아니라 bfs를 쓴다.

 

package com.baekJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;

public class BJ_G5_14395_4연산 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	static long s,t;
	static Set<Long> list;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		input = new BufferedReader(new StringReader(src));
		tokens = new StringTokenizer(input.readLine());
		
		s = Integer.parseInt(tokens.nextToken());
		t = Integer.parseInt(tokens.nextToken());
		
		list = new HashSet<Long>();
		if(s == t) {
			System.out.println(0);
		}else {
			bfs(s);
		}
	}

	private static void bfs(long s) {
		Queue<Node> queue = new LinkedList<>();
		queue.offer(new Node(s, ""));
		list.add(s);
		while(!queue.isEmpty()) {
			Node front = queue.poll();
			if(front.num == t) {
				System.out.println(front.str);
				return;
			}
			
			for(int d=0; d<4; d++) {
				long nn = 0;
				switch (d) {
				case 0:
					nn = front.num * front.num;
					break;
				case 1:
					nn = front.num + front.num;
					break;
				case 2:
					nn = front.num - front.num;
					break;
				case 3:
					if(front.num == 0) continue;
					nn = front.num / front.num;
					break;
				}
				if(!list.contains(nn)) {
					list.add(nn);
					queue.offer(new Node(nn, front.str + dir[d]));
				}
			}
		}
		System.out.println(-1);
		return;
	}
	
	static char[] dir = { '*', '+', '-', '/' };
	
	static class Node{
		long num;
		String str;
		public Node(long num, String str) {
			super();
			this.num = num;
			this.str = str;
		}
	}

	static String src =
			"10 1";
}

 

 

후기

 

 솔직히 말하면 솔루션을 봤다.

맨날 배열을 4방 탐색하는 것만 주구장창하다가 이런식의 bfs가 나오니까 아무 생각도 안나는 멍청이가 되어버렸다.

막상 솔루션을 보니 이렇게 허무할수가.. 정말 간단한 문제였다.

너무 정형화된 문제만 풀지 말고 색다른 문제들도 많이 풀어야 한다는 것을 뼈저리게 느꼈다.