[백준] 단계별로 풀어보기(단계:27, 동적 계획법과 최단거리 역추적,JAVA)9019번, DSLR

문제 링크

9019번: DSLR

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

동적 계획법

모든 연산을 수행하면 똑같은 연산을 중복되게 수행하게 되는데 다이나믹 프로그램은 연산한 내용을 따로 저장하여 효율적으로 작성한 프로그램입니다.

 

더 자세한 내용은 링크를 남겨두겠습니다.

동적 계획법 - 위키백과, 우리 모두의 백과사전

이 문제에 핵심은

1. 증가하는 수열 중 가장 긴 수열의 길이를 결과로 출력해야 합니다.

 

배열

 

visited[] : 해당 숫자에 탐색하였는지 확인하는 함수

 

문제에 나온 연산을 점화식으로 표현하면

 

연산 D

 

2n mod 10000

 

연산 S

 

n-1<0 ? 9999 : n-1

 

연산 L

 

n%1000 * 10 + n/1000

 

연산 R

 

n/10 + n%10 * 1000

 

 

위 연산을 BFS탐색을 통해 가장 먼저 B의 값에 도착할 때에 과정을 결과로 출력하면됩니다.

 

예제입력1

초기값

A = 1234, B = 3412 일 때

 

D = 2468, S = 1233, L = 2341, R = 4123

 

D명령어 결과 탐색

A = 2468, B = 3412

 

D = 4936. S = 2467, L = 4682, R = 8246

 

S명령어 결과 탐색

A = 1233, B = 3412

 

D = 2466. S = 1232, L = 2331, R = 3123

 

L명령어 결과 탐색

A = 2341, B = 3412

 

D = 4682. S = 2340, L = 3412, R = 1234

 

B값 최초 도착에 해당하는 프로세스 L -> L이므로

 

결과가 "LL"이 출력됩니다.

 

 

문제를 해결한 알고리즘의 과정입니다.

1. A와 B를 받습니다.

2. BFS와 visited[]을 이용하여 DSLR 명령어를 탐색합니다.

3. 가장 먼저 B에 도착한 과정을 BufferedWriter 저장합니다.

4. T번의 A와 B에 프로세스를 찾은 후 BufferedWriter에 저장된 프로세스들을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 이용하여 T개의 A와B를 나누었습니다.
• BFS와 visited[]를 이용하여 B에 도착하는 최단 프로세스를 구하는 bfs함수를 실행하였습니다.
• BufferedWriter에 T번의 A와 B에 대한 최단 프로세스를 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• bfs함수는 BFS와 visited를 이용하여 DSLR 명령어에 따른 목적값 B에 도착하는 최소 프로세스를 구하였습니다.

import java.io.*;
import java.util.*;
public class Main{
	//BFS에 사용하는 큐에 생성자
	static class move{
		String process;		//명령어 과정 저장 변수
		int num;		//현재 숫자 저장 변수
		public int getNum() {
			return num;
		}
		public String getProcess() {
			return process;
		}
		public move(String process, int num) {
			this.process = process;
			this.num = num;
		}
	}
	static int T;		//테스트 개수 저장 변수
	static boolean[] visited;		//해당 숫자 방문 확인 배열
	public static void main(String[] arg) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        	//입력값 처리하는 BufferedReader
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        	//결과값 출력하는 BufferedWriter
		StringTokenizer st;
		T = Integer.parseInt(br.readLine());
		for(int i=0;i<T;i++) {
			st = new StringTokenizer(br.readLine()," ");
			visited = new boolean[10000];		//숫자 방문 배열 초기화
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
			String result = bfs(A,B);		//BFS탐색하는 함수 실행 및 결과 저장
			bw.write(result + "\n");		//프로세스 BufferedWriter 저장
		}
		bw.flush();		//결과 출력
		bw.close();
		br.close();
	}
    	//-------BFS와 DSLR명령어를 이용하여 최단 프로세스를 구하는 함수-------
	static String bfs(int start, int end) {
		Queue<move> queue = new LinkedList<move>();	
		queue.add(new move("", start));		//초기값 저장
		while(!queue.isEmpty()) {
			move temp = queue.poll();
			int num = temp.getNum();
			String process = temp.getProcess();
			if(num == end)		//B 숫자 도착했을 때
				return process;
			
			int n = (num*2)%10000;		//명령어 D
			if(!visited[n]) {
				visited[n] = true;
				queue.add(new move(process + "D",n));
			}
			n = num-1<0?9999:num-1;		//명령어 S
			if(!visited[n]) {
				visited[n] = true;
				queue.add(new move(process + "S", n));
			}
			n = num/1000 + (num%1000)*10;	//명령어 L
			if(!visited[n]) {
				visited[n] = true;
				queue.add(new move(process + "L", n));
			}
			n = num/10 + (num%10)*1000;		//명령어 R
			if(!visited[n]) {
				visited[n] = true;
				queue.add(new move(process + "R", n));
			}
		}
		return "";
	}

}