백준 14395 - 4연산

Java

14395 번 - 4연산

문제

접근 방법

연산을 통해 처음 도달한 값이, 최소 연산 횟수이므로 최단거리를 구하는 BFS를 사용한다.

비슷한 문제로는 백준 A → B이 있다.

코드

Main {
	static int n, m, result;
	static final int MAX = 1000000001;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	n = stoi(stk.nextToken());
    	m = stoi(stk.nextToken());

    	System.out.print(BFS(n,m));

    	br.close();
	}


	static String BFS(int start, int end) {
		if(start == end)
			return "0";

		boolean[] vis = new boolean[MAX];
		vis[start] = true;

		Queue<Data> queue = new LinkedList<Data>();
		queue.add(new Data(start, ""));

		long curN, nextN;
		int idx;
		String curS;
		Data data;
		while(!queue.isEmpty()) {
			data = queue.poll();
			curN = data.getCurN();
			curS = data.getStr();

			if(curN == end) {
				return curS;
			}
			// 3. s = s * s; (출력: *)
			nextN = curN * curN;
			if(isIn(nextN)) {
				idx = (int) nextN;
				if(!vis[idx]) {
					vis[idx] = true;
					queue.add(new Data(nextN, curS.concat("*")));
				}
			}
			// 1. s = s + s; (출력: +)
			nextN = curN * 2;
			if(isIn(nextN)) {
				idx = (int) nextN;
				if(!vis[idx]) {
					vis[idx] = true;
					queue.add(new Data(nextN, curS.concat("+")));
				}
			}
			// 2. s = s - s; (출력: -)
			idx = 0;
			if(!vis[idx]) {
				vis[idx] = true;
				queue.add(new Data(idx, curS.concat("-")));
			}

			// 4. s = s / s; (출력: /) (s가 0이 아닐때만 사용 가능)
			if(curN != 0) {
				idx = 1;
				if(!vis[idx]) {
					vis[idx] = true;
					queue.add(new Data(idx, curS.concat("/")));
				}
			}
		}

		return "-1";
	}

	static class Data {
		long curN;
		String str;

		Data(long num, String s){
			curN = num;
			str = s;
		}

		public String getStr() {
			return str;
		}

		public long getCurN() {
			return curN;
		}
	}

	// 주어진 범위 안에 있는가
    public static boolean isIn(long y){
        if(y < 0 || y >= MAX)
            return false;
        return true;
    }

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

개선할 점