[백준 9019] DSLR (JAVA)

🔰 문제

백준 9019번: DSLR (Gold 4)

💡 접근방식

처음엔 그리디 문제라 생각했다.

1. 문자열의 개수 같으면 문자 요소 같은지 체크
2. 같으면 L과 R 모두 실행해봐서 더 적은 횟수인 연산 진행
3. L과 R 연산 불가능할 경우, A와 B 대소 비교
	3-1. A>B이면 S 연산
    3-2. A<B이면 D 연산

그러나 위와 같이 풀면, 다음과 같은 반례가 발생한다.
A: 90 B: 9 인 경우
위의 로직으로 풀면 A와 B의 자리수가 다르기 때문에 A를 B와 자리수가 같아질 때까지 D 연산을 81번 하게 된다.

하지만 정답은 A를 L 연산 1번만 해주면 되기 때문에 잘못 된 로직이다.
그래서 결론은 내가 머리를 끙끙 앓지 말고, 그냥 D, L, S, R 가능한 모든 경우의 수에 대해 가지를 뻗어나가며 컴퓨터가 알아서 계산한 후 판단하도록 냅둬야 하는 것이다.

그러기 위해서 BFS를 사용하는 문제이다.

여기서 1차 충격이 왔다.
DFS/BFS 문제를 풀 때 대부분 그래프 탐색 문제를 풀어서인지 이렇게 사용될 수 있다는 것을 몰랐다... 경우의 수를 가지 뻗어나갈 때 BFS를 쓸 수 있다는 것을 새로 알게 되었다.

또한 이번 좌측으로 회전, 우측으로 회전하는 문제 유형은 자주 접할 수 있었는데 이번 문제는 문자열이 아닌 숫자였다. 숫자를 문자열로 변환하여 회전시키려 하니 너무 복잡했는데 숫자도 회전하는 방식이 있다.

숫자 회전 방식

//우측 회전 1234 -> 4123
numL = (num%10)*1000 + num/10;

//좌측 회전 1234 -> 2341
numR = (num%1000)*10+num/1000;

🕑 소요시간

1시간 반 +

로직 힌트 얻고, 다시 풀음

💻 풀이

import java.io.*;
import java.util.*;

public class Main_9019_2 {
	static int A, B;
	static boolean visited[];
	static String cmd[];
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T=Integer.parseInt(br.readLine());
		for(int t=1;t<=T;t++) {

			StringTokenizer st = new StringTokenizer(br.readLine());
			A = Integer.parseInt(st.nextToken());
			B = Integer.parseInt(st.nextToken());
			visited = new boolean[10000];
			cmd = new String[10000];
			Arrays.fill(cmd, "");
			
			bfs();
			System.out.println(cmd[B]);
			
		}
	}
	private static void bfs() {
		Queue<Integer> q = new LinkedList<>();
		q.add(A);
		visited[A]=true;
		
		while(!q.isEmpty() && !visited[B]) {
			int cur = q.poll();
			int D = cur*2>9999?(cur*2)%10000:cur*2;
			int S = (cur-1)>=0?cur-1:9999;
			int L = (cur%1000)*10+cur/1000;
			int R = (cur%10)*1000+cur/10;

			if(!visited[D]) {
				q.add(D);
				visited[D]=true;
				cmd[D] = cmd[cur]+"D";
			}
			if(!visited[S]) {
				q.add(S);
				visited[S]=true;
				cmd[S] = cmd[cur]+"S";
			}
			if(!visited[L]) {
				q.add(L);
				visited[L]=true;
				cmd[L] = cmd[cur]+"L";
			}
			if(!visited[R]) {
				q.add(R);
				visited[R]=true;
				cmd[R] = cmd[cur]+"R";
			}
		}
	}
}

🌟 비슷한 유형의 문제들

참고

[백준] 9019번 자바 DSLR