백준 9019번 DSLR 풀이 (JAVA)

9019번: DSLR (acmicpc.net)

9019번: DSLR

solved.ac에서 gold 문제를 그냥 아무거나 풀어보자 해서 문제를 골랐고 문제를 풀기 전에 알고리즘 분류를 확인한 나는 그래프 탐색 문제라길래 오랜만에 BFS 문제나 빨리 풀어보자는 생각을 하게 됐다. 그러나 문제를 보면서 난 BFS를 여전히 잘 모르는구나라는 생각을 하게 되었고 이 문제를 풀면서 BFS를 좀 더 이해하게 됐다(사실 지금도 완벽히 안 지는 잘 모르겠다)

 

일단 이 문제는 이 문제가 BFS로 풀 수 있는 문제인지를 눈치채야 한다.

아마 알고리즘 분류에 써있지 않았다면 나는 이 문제가 BFS 문제인지도 한~~~~~참 뒤에 깨닫게 되었을 것이다.

(다른 풀이들을 보면 어떻게 이 문제가 다들 BFS 문제인지 바로 안 것인지 다들 너무 대단하다.)

 

이 문제가 BFS로 풀 수 있는 이유는 A에서 B로 변환하기 위해 최소한의 명령 케이스를 구하는 것이기 때문이다.

BFS는 기본적으로 현재 가능한 케이스들을 모두 해보고 그 다음 단계로 넘어간다. 예를 들면 아래와 같다.

 

BFS로 DSLR 명령어 나열 케이스 탐색 예시

그림이 너무 길어져서  1단계의 S,L,R의 탐색 케이스는 생략했다. 그림에서 보면 첫번째 단계부터 다음 단계에 가능한 명령어 DSLR을 연산해보고 우리가 구하고자 하는 값이 아니면 다시 DSLR 명령어를 차례로 연산해보고...이걸 반복한다.

그런데 현재 단계에서 모든 가능한 케이스를 해봤는데 구하고자 하는 B가 나왔다?!? 그러면 당연히 이게 최소 단계로 구한 최소한의 명령어 나열 케이스를 구한 것이 되는 것이다. 다음 단계로 간다는 것은 거쳐야 하는 명령어가 +1 된다는 것을 의미한다는 것이기 때문이다!

말이 중언부언되는거 같긴 하지만 나의 미약한 설명이 누군가에게 도움이 되길 바라며...아래 코드도 남긴다.

이 문제는 참고로 시간초과가 잘 나기 때문에 (시간 제한이 6초임에도... visited를 확인 잘 안해서 여러번 시간초과가 났다ㅠㅠ) 꼭 이 값을 체크 했는지 확인하는 절차가 필요하다.

/**
 * 테스트케이스로 주어지는 A, B가 모두 0~9999 숫자 중 하나이니 
 * 0~9999 숫자가 들어 있는 배열을 준비하고
 * BFS로 그 배열 위치까지 가는 최소 연산의 값과 연산의 방법을 저장해 놓을 수 있음
 * (BFS가 일단 가능한 DSLR의 연산을 모두 해보고 그 값에 이미 최소의 방법이 저장되어 있지 않으면 
 *  최소의 값을 저장하고 또 DSLR의 모든 연산을 해보므로 결국 가장 최소의 방법이 항상 저장되게 되어 있음
 *  BFS의 순서가  1차 DSLR 연산 -> 2차 DSLR 연산 -> 3차 DSLR 연산 -> ....... 
 *  지금 상황에서 가능한 모든 간선을 타면서 최단 경로를 찾아줌)
 * (그러나 문제 분류를 보기 전에는 BFS 문제인지 알기 어려운거 같은데...나만 그런가..?!?!?!)
 * */

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int testCaseN = sc.nextInt();
		
		String[] answer = new String[testCaseN];
		for(int i=0; i<testCaseN; i++){
			int A=sc.nextInt();
			int B=sc.nextInt();
			answer[i] = getLeastPath(A,B);
		}

		for(String a : answer){
			System.out.println(a);
		}
		
	}
	
	static public String getLeastPath(int A, int B){
		Queue<NumberPath> queue = new LinkedList<NumberPath>();
		boolean[] visited = new boolean[10000];
		
		int curNum = 0;
		String curPath = "";
		
		visited[A] = true;
		queue.offer(new NumberPath(A,curPath));
		while(!queue.isEmpty()){
			NumberPath cur = queue.poll();
			curNum = cur.number;
			curPath = cur.path;
			
			if(curNum == B){
                queue.clear();
				break;
			}
			
			//D 연산으로 새로운 숫자 방문 -> 방문한 적 없는 숫자이면 queue 에 넣기
			int newNum = (curNum*2)%10000;
			if(!visited[newNum]){
				visited[newNum] = true;
				queue.offer(new NumberPath(newNum, curPath+"D"));
			}
			
			//S 연산으로 새로운 숫자 방문
			newNum = (curNum == 0)? 9999: curNum-1; //생각없이 문제를 따라치다보면 여기서 실수를 하게 됨
			if(!visited[newNum]){
				visited[newNum] = true;
				queue.offer(new NumberPath(newNum, curPath+"S"));
			}
			
			//L 연산으로 새로운 숫자 방문
			int d4 = curNum%10; 
			int d3 = (curNum/10)%10;
			int d2 = (curNum/100)%10;
			int d1 = (curNum/1000)%10;
			
			newNum = (((d2*10 + d3)*10)+d4)*10+d1;
			if(!visited[newNum]){
				visited[newNum] = true;
				queue.offer(new NumberPath(newNum, curPath+"L"));
			}
			
			//R 연산으로 새로운 숫자 방문
			newNum = (((d4*10 + d1)*10)+d2)*10+d3;
			if(!visited[newNum]){
				visited[newNum] = true;
				queue.offer(new NumberPath(newNum, curPath+"R"));
			}				
		}
		
		return curPath;
	}

}

class NumberPath{
	int number;
	String path;
	
	public NumberPath(int N, String P){
		this.number = N;
		this.path = P;
	}
}