[Baekjoon] 14395_4연산

Gold V

문제(출처: https://www.acmicpc.net/problem/14395)

---

< 4연산 >

 

문제 풀이

 

bfs를 활용하여 s를 t로 바꾸는 방법을 찾았다. 

처음에는 방문 배열을 사용하려 했지만 범위가 넘어가 에러가 발생하였다. 찾아보니 그래서 사람들이 set을 쓰는 거였다. 

set을 활용하여 중복 확인을 하여 문제를 해결할 수 있었다.

 

 

 - my solution (Java)

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

public class _14395_ { // 4연산

	public static void main(String[] args) throws IOException {
		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(bf.readLine());

		long s=Integer.parseInt(st.nextToken());
		long t=Integer.parseInt(st.nextToken());

		HashSet<Long>set=new HashSet<>();
		String result="";

		// s와 t가 같은 경우
		if(s==t) System.out.println(0);
		else { // s와 t가 다른 경우
			Queue<Info>queue=new LinkedList<>();
			queue.add(new Info(s, ""));
			set.add(s);

			while(!queue.isEmpty()) {
				Info info=queue.poll();
				long arr[]= {info.value*info.value,info.value+info.value, 0, 1}; // *, +, -, /
				for(int i=0; i<4; i++) {
					if(!set.contains(arr[i])) {
						String str=info.cal;
						if(i==3 && info.value==0) break;
						if(i==0)str+="*";
						else if(i==1) str+="+";
						else if(i==2) str+="-";
						else if(i==3) str+="/";
						if(arr[i]==t) {
							result=str;
							break;
						}
						set.add(arr[i]);
						queue.add(new Info(arr[i], str));
					}
				}
				if(!result.equals("")) break;
			}
			if(result.equals("")) System.out.println(-1); // 바꿀 수 없는 경우
			else System.out.println(result);
		}
	}

	static class Info{
		long value; // 값
		String cal; // 방법
		public Info(long value, String cal) {
			this.value=value;
			this.cal=cal;
		}
	}
}

 

Main

- s와 t 입력

- set : 중복 여부를 판별하기 위해 Hashset 선언

- s와 t가 같은 경우 0 출력

- s와 t가 다른 경우 bfs 탐색 -> queue가 빌 때까지 반복하여 *, +, -, / 순으로 연산하여 아직 set에 없는 값이면 set과 queue에 넣어주기 -> t로 바꿨으면 종료

- 바꿀 수 없는 경우에는 -1 출력, 바꾼 경우에는 result 출력

---

생각🤔

 

visited 범위 때문에 에러가 났던 것 같다... set 쓸 생각을 왜 못했는지.. 더 분발하자

 

---