[백준]DSLR(9019번)

https://www.acmicpc.net/problem/9019
//1 문제 분석

너비 우선 탐색을 통해 최단경로를 찾는 문제이다. 다만 L과 R은 좀 독특한 방식으로 움직인다.

//2 문제 해결

4자리수 정수를 크기 4의 배열로 바꾸는 메서드와 반대로 배열을 정수로 바꾸는 메서드를 짜서 L과 R을 해결하였다. 방문 배열에는 이전에 방문했던 지점을 기록하고, 다른 배열에는 이전 명령어(DSLR)을 저장해서 마지막 지점에서 역순으로 커맨드를 탐색해 과정을 출력할 수 있도록 하였다.

//3 작성 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;

public class DSLR_9019 {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer stz;
		int T = Integer.parseInt(br.readLine());
		for (int i = 0 ; i<T ; i++) {
			int[] visited = new int[10000];	
			char[] command = new char[10000];
			stz = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(stz.nextToken());
			int end = Integer.parseInt(stz.nextToken());
			bfs(visited,command,start,end);
			ArrayDeque<Character> ans = new ArrayDeque<>();
			int point = end;
			while(point!=start) {
				ans.addFirst(command[point]);
				point = visited[point]-1;
			}
 			while(!ans.isEmpty()) {
 				sb.append(String.valueOf(ans.poll()));
 			}
 			sb.append("\n");
		}
		System.out.println(sb);
	}
	static int[] intToArr(int n) {
		int[] ans = new int[4];
		for (int i = 3 ; i>=0 ; i--) {
			ans[i]=n%10;
			n/=10;
		}
		return ans;
	}
	static int arrToInt(int[] arr) {
		int ans = 0;
		int tens = 1;
		for (int i = 3; i>=0 ; i--) {
			ans+=arr[i]*tens;
			tens*=10;
		}
		return ans;
	}
	static int left(int temp) {
		int[] arr = intToArr(temp);
		int[] Larr = new int[4];
		for (int i = 0 ; i<4 ;i++) {
			Larr[i]=arr[(i+1)%4];
		}
		return arrToInt(Larr); 
	}
	static int right(int temp) {
		int[] arr = intToArr(temp);
		int[] Rarr = new int[4];
		for (int i = 0 ; i<4 ;i++) {
			Rarr[i]=arr[(i-1+4)%4];
		}
		return arrToInt(Rarr); 
	}
	static void bfs(int[] visited, char[] command, int start, int end) {
		ArrayDeque<Integer> q = new ArrayDeque<>();
		q.add(start);
		visited[start]=-1;						
 		while(!q.isEmpty()) {
 			int temp = q.poll();
 			int[] npoint= {(temp*2)%10000,(temp-1+10000)%10000,left(temp),right(temp)};
 			char[] com = {'D','S','L','R'};
 			for (int i = 0 ; i<4 ; i++) {
 				if (visited[npoint[i]]==0) {
 	 				q.add(npoint[i]);
 	 				visited[npoint[i]]=temp+1;
 	 				command[npoint[i]]=com[i];
 	 				if(npoint[i]==end) return;
 	 			}
 			}
		}
	} 
}

//4 시행착오

방문 배열을 저장할 때 이전 지점을 저장하였다. 하지만 이 경우 0지점에서 오는 경우 0이 저장되어 방문처리가 되지 않았다. 그래서 코드에서 메모리 초과 현상이 일어났었다.

//5 개선 가능성

L과 R 계산을 정수를 배열로 저장후 바꾸는 작업을 하였는데 사실 그렇게 번거로운 작업을 하지 않아도 구현이 가능할 것이다.