https://www.acmicpc.net/problem/14395
14395번: 4연산
첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다. 연산의 아
www.acmicpc.net
코드설명
BFS 문제에 자료형 범위를 고려해야합니다.
항상 이러한 문제를 보면 DFS로 풀지, BFS로 풀지 고민이 됩니다.
이 문제는 BFS로 접근하는데는 성공하였지만, 명확한 근거를 가지고서 어떤 알고리즘을 사용할지 생각이 필요합니다.
일차적으로 BFS와 DFS 둘다 사용가능할지 생각하는 과정이 꼭 필요한 것 같습니다.
처음에 풀었을때는 t
첫째 줄에 s와 t가 주어진다. (1 ≤ s, t ≤ 10^9)
처음에 10^9 을 보고, 10억의 범위이니 굳이 Integer를 써야겠다라고 생각했습니다.
그래서 visited[10^9]을 선언하고, 진행하였고, 그 과정에서 Overflow가 날 가능성은
s = s * s 를 할 경우이기에 Math.sqrt(10^9) 의 값 이내에 있을때만 가능하도록 설정하였지만 계속해서 Array OutofBound가 나왔습니다.
그렇기에 long 형으로 선언하고, visited[] 배열 대신 HashSet을 활용하여 중복처리를 진행했습니다.
이 과정에서 아래와 같이 일종의 범위를 다스리며 진행하려고하였지만, 그렇게 할경우 최소경로를 구하는 방식을 해치는 것 같습니다. 그렇기에 조건을 해제하고 진행하면 됩니다.
next >= 1 && next <= MAX
이 문제에서 처음에는 DFS를 통해 진행하려고하였지만, 최소연산횟수를 구하는것이므로 BFS를 사용하면 쉽게 해결할 수 있습니다.
코드
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 Main { public static long s, t; public static long MAX = 100000000; public static String answer=""; public static HashSet<Long> hashset = new HashSet<>(); 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()); if(s == t) { System.out.println(0); return ; } simulate(new Node(s, "")); if(answer.length() == 0) { System.out.println("-1"); }else { System.out.println(answer); } } public static void simulate(Node start) { //일반 Queue<Node> q = new LinkedList<>(); q.offer(start); hashset.add(start.num); while(!q.isEmpty()) { Node temp = q.poll(); long num = temp.num; String str = temp.str; if(num == t) { answer = str; return ; } long next = 0; next = num * num; // System.out.println("next:"+next); if(!hashset.contains(next)) { hashset.add(next); q.offer(new Node(next, str + "*")); } next = num + num; if(!hashset.contains(next)) { hashset.add(next); q.offer(new Node(next, str + "+")); } next = num - num; if(!hashset.contains(next)) { hashset.add(next); q.offer(new Node(next, str + "-")); } if(num != 0) { next = 1; if(!hashset.contains(next)) { hashset.add(next); q.offer(new Node(next, str + "/")); } } } } } class Node{ long num; String str; public Node(long num, String str) { this.num = num; this.str = str; } }
처음에 visited를 활용한 코드. 이렇게 할경우, Math.sqrt로 곱하기 이후에도 값이 올바르게 나오게하기 위한 처리
하지만 ArrayIndexOutofExcpeiton 이 뜹니다.
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 Main { public static int s, t; public static int MAX = 100000000; public static String answer=""; public static boolean[] visited = new boolean[1000000000]; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); s = Integer.parseInt(st.nextToken()); t = Integer.parseInt(st.nextToken()); simulate(new Node(s, "")); System.out.println(answer); } public static void simulate(Node start) { //일반 Queue<Node> q = new LinkedList<>(); q.offer(start); visited[start.num] = true; while(!q.isEmpty()) { Node temp = q.poll(); int num = temp.num; String str = temp.str; if(num == t) { answer = str; return ; } int next = 0; next = num * num; System.out.println("next:"+next); if(visited[next] == false && next >= 1 && next <= Math.sqrt(MAX) ) { visited[next] = true; q.offer(new Node(next, str + "*")); } next = num + num; if(visited[next] == false && next >= 1 && next <= MAX) { visited[next] = true; q.offer(new Node(next, str + "+")); } next = num - num; if(visited[next] == false && next >= 1 && next <= MAX) { visited[next] = true; q.offer(new Node(next, str + "-")); } if(num != 0) { next = 1; if(visited[next] == false && next >= 1 && next <= MAX) { visited[next] = true; q.offer(new Node(next, str + "*")); } } } } } class Node{ int num; String str; public Node(int num, String str) { this.num = num; this.str = str; } }
'알고리즘 > 백준' 카테고리의 다른 글
[백준] 16194 카드 구매하기 2 - DP JAVA (0) | 2023.09.13 |
---|---|
[백준] 11052 카드 구매하기 - DP JAVA (0) | 2023.09.13 |
[백준] 10026 적록색약 - BFS JAVA (0) | 2023.09.12 |
[백준] 1963 소수 경로 - BFS + 에라토스테네스의 체 + 소수 판정 JAVA (0) | 2023.09.12 |
[백준] 3055 탈출 - BFS JAVA (0) | 2023.09.12 |