백준[9019] DSLR (JAVA)

https://www.acmicpc.net/problem/9019

9019번: DSLR

 

 

비슷한 문제를 조금 풀어봤다면 간단히 해결가능한 탐색문제이다.

 

DSLR 각 명령어에 해당하는 좌표로 이동할때 D,S 명령어에 해당하는것은 누구나 쉽게 작성가능하지만,

 

L,R에 해당하는 명령어를 문자열 변환을 사용해 이리저리 비틀어 풀려 하면 꼬이게 되는 문제이다.

 

이때 사용가능한 아이디어는 수식을 사용해 한칸씩 미루거나 땡겨오는 방법을 사용하는것으로,

 

https://0bliviat3.tistory.com/31

[백준 16953] A → B (JAVA)

 

위 문제 풀이시 사용했던 방법과 유사하다.

 

다만 자릿수에 해당하는 수를 수식으로 잘라와 새로 재구성한다는 점은 조금 차이가 있다.

 

그렇다면 바로 코드로 풀이해보겠다.

 

우선 다음칸으로 이동할 때마다 필요한 정보가 이전에 방문했었는가, 그리고 현재까지의 명령어,

그리고 이전숫자에 대한 정보를 갖고있어야 한다.

이때 방문처리는 그냥 방문배열하나 선언을 통해 해결을 한다해도, 명령어와 숫자에 대한 정보는

각 노드마다 상이하므로 하나의 클래스를 만들어 저장할 수 있도록 하겠다.

 

class Resister {
	int num;
	String commend;
	
	Resister(int num, String commend){
		this.num = num;
		this.commend = commend;
	}
}

 

 

BFS를 사용해 탐색할것이므로 큐, 그리고 방문배열을 하나 선언해주고,

 

여러번의 테스트케이스가 있으므로 초기화 메소드도 하나 선언해주도록 하겠다.

 

	static boolean[] visit;
	static Resister[] queue;
	static int front, rear;
	
	static void clear() {
		front = rear = 0;
		visit = new boolean[10000];
		queue = new Resister[10000];
	}

 

 

이제 각 명령어에 따라 새로운 칸과 새로운 명령어가 추가된 데이터를 생성해줄

메소드를 하나 만들도록 하겠다.

 

D의 경우 두배 후 10000으로 나눈 나머지,

S는 1씩 감소, 만약 감소한 값이 -1인 경우 9999로 저장

L은 왼쪽으로 회전이므로 이전의 수의 첫번째자리수를 나누기연산으로 구하고 이전의수를 나머지연산을 통해

둘쨋자리수부터 마지막자리 수까지 구해서 10을 곱한뒤 더해주면 된다.

 

R은 오른쪽으로 회전이므로 이전의 수의 마지막자리수를 1000을 곱하고 이전의수를 10으로 나눈 몫과 더해주면 된다.

 

이 과정을 인자로 받는 명령어에 따라 새로운 Resister 객체를 만들어 리턴해주도록 한다.

 

	static Resister getNext(Resister now, char commend) {
		int num = now.num;
		if(commend == 'D') {
			num = (num << 1)%10000;
		}else if(commend == 'S') {
			num--;
			if(num == -1) num = 9999;
		}else if(commend == 'L') {
			num = num/1000 + (num%1000)*10;
		}else {
			num = (num%10)*1000 + num/10;
		}
		return new Resister(num, now.commend + commend);
	}

 

 

다음은 각 명령어를 문자자료형으로 넘겨주고 받아오므로 반복문을 통해 메소드를 호출해

다음 값을 받아올 수 있도록 명령어 배열을 하나 선언해준다.

 

	static char[] commend = { 'D' , 'S' , 'L' , 'R' };

 

 

이제 남은 것은 BFS 탐색을 통해 현재구하려는 수와 일치하면 리턴해줄수 있도록

메소드를 만들어주는 것이다.

 

	static String bfs(int a, int b) {
		queue[rear++] = new Resister(a, new String());
		visit[a] = true;
		while(queue[front] != null) {
			Resister now = queue[front];
			queue[front++] = null;
			front%=10000;
			for(int i = 0; i < 4; i++) {
				Resister next = getNext(now,commend[i]);
				if(next.num == b) return next.commend;
				if(!visit[next.num]) {
					queue[rear++] = next;
					visit[next.num] = true;
					rear%=10000;
				}
			}
		}
		return null;
	}

 

이와 같이 작성후 예제를 실행해보면 답과 일치하는것을 확인 할수 있다.

 

 

 

아래는 코드의 전문이다.

 

package boj4;

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

public class Boj9019 {
	
	/*
	 * 제출 完
	 */
	
	static char[] commend = { 'D' , 'S' , 'L' , 'R' };
	static boolean[] visit;
	static Resister[] queue;
	static int front, rear;
	
	static void clear() {
		front = rear = 0;
		visit = new boolean[10000];
		queue = new Resister[10000];
	}
	
	static Resister getNext(Resister now, char commend) {
		int num = now.num;
		if(commend == 'D') {
			num = (num << 1)%10000;
		}else if(commend == 'S') {
			num--;
			if(num == -1) num = 9999;
		}else if(commend == 'L') {
			num = num/1000 + (num%1000)*10;
		}else {
			num = (num%10)*1000 + num/10;
		}
		return new Resister(num, now.commend + commend);
	}
	
	
	static String bfs(int a, int b) {
		queue[rear++] = new Resister(a, new String());
		visit[a] = true;
		while(queue[front] != null) {
			Resister now = queue[front];
			queue[front++] = null;
			front%=10000;
			for(int i = 0; i < 4; i++) {
				Resister next = getNext(now,commend[i]);
				if(next.num == b) return next.commend;
				if(!visit[next.num]) {
					queue[rear++] = next;
					visit[next.num] = true;
					rear%=10000;
				}
			}
		}
		return null;
	}
	


	public static void main(String[] args) throws IOException{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		int t = Integer.parseInt(in.readLine());
		
		while(t-- > 0) {
			st = new StringTokenizer(in.readLine()," ");
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			clear();
			sb.append(bfs(a,b)).append('\n');
		}
		
		in.close();
		
		System.out.print(sb);
	}
	
}

class Resister {
	int num;
	String commend;
	
	Resister(int num, String commend){
		this.num = num;
		this.commend = commend;
	}
}