[알고리즘] Java / 백준 / DSLR / 9019

[알고리즘] Java / 백준 / DSLR / 9019

문제

문제 링크

접근 방식

처음엔 단순히 bfs의 큐에 현재 숫자와 문자열을 가지는 객체를 넣어 탐색하였으나 시간이 너무 오래 걸렸다. 그 이유는 문자열을 계속 복사해서 현재 객체의 문자열에 넣는 방식이다.

1. 문자열을 저장하지 않고 B를 찾은 후 역방향으로 탐색할 수 있도록 부모의 수를 나타내는 배열을 만든다.
2. 각 수에 도달하기 위해 사용한 명령어를 저장하는 배열을 만든다.
3. bfs를 통해 B를 찾을 때까지 부모 배열과 명령어 배열을 채운다
4. B를 찾으면 B에서 A까지 역순으로 명령어를 저장하고 역순으로 출력한다

코드

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

public class Main_9019 {

	static char[] chars = {'D','S','L','R'};
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		
		StringTokenizer st;
		while(T-->0) {
			st = new StringTokenizer(br.readLine());
			
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
			
			bfs(A,B);
		}
	}
	
	public static void bfs(int start, int target) {
		
		
		int parent[] = new int[10000];
		Arrays.fill(parent, -1);
		char commands[] = new char[10000];
		
		Queue<Integer> que = new LinkedList<>();
		que.add(start);
		
		while(!que.isEmpty()) {
			
			int now = que.poll();
			
			if(parent[target] != -1) { // target에 도달한 적이 있으면 탈출 
				break;
			}
			
			for(int i=0;i<4;i++) {
				int res = cal(now, i);
				if(parent[res] == -1) {
					parent[res] = now;
					commands[res] = chars[i];
					que.add(res);
				}
			}
		}
		
		StringBuilder sb = new StringBuilder();
		
		while(target != start) {
			sb.append(commands[target]);
			target = parent[target];
		}
		
		sb = sb.reverse();
		System.out.println(sb);
		
	}
	
	public static int cal(int n, int command) {
		
		int res = 0;
		
		switch(command) {
		case 0:
			res = n*2 % 10000;
			break;
		case 1:
			res = n == 0? 9999 : n-1;
			break;
		case 2:
			res = (n / 1000) + (n % 1000) * 10;
			break;
		case 3:
			res = (n / 10) + (n % 10 * 1000);
			break;
		}
		
		return res;
	}
}