[백준/Java] 9019 DSLR

박찬병·2024년 10월 12일

Problem Solving boj 백준

Problem Solving

목록 보기

13/48

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

문제 요약

D, S, L, R 4가지 명령어를 수행할 수 있는 계산기가 있다.
계산기는 0이상, 9999이하의 수 n만 계산할 수 있다.

D는 n을 두 배로 바꾼다. 만약 그 결과가 1만이 넘으면 1만으로 나눈 나머지를 얻는다.
S는 n에서 1을 뺀다. 만약 결과가 -1이라면 9999를 얻는다.
L은 n의 각 자릿수를 왼쪽으로 회전시킨다.
R은 n의 각 자릿수를 오른쪽으로 회전시킨다.

L과 R에서 n이 네자릿수가 아니었다면 빈 자릿수는 0이라고 생각하면 된다.

테스트 케이스 T개가 주어진다.
이 계산기를 이용하여 입력 수 A를 다른 숫자 B로 바꾸는 최소의 명령어를 얻어라.
가능한 명령이 여러가지라면 아무거나 출력한다.

문제 접근

이러한 문제는 보통 모든 경우를 다 해보면 정답을 얻을 수 있다.
문제 상황을 그래프로 해석하면, 각 숫자는 node이며 각 연산은 edge로 생각할 수 있다.
그러면 1만 개의 노드와 4만 개의 엣지로 이루어진 그래프임을 알 수 있다.
다익스트라 알고리즘을 사용하면 하나의 노드에서 다른 노드까지의 최단거리를 구할 수 있으며, 이때의 시간복잡도는 $O(ElogV)$ 이다.
따라서 이러한 문제가 T번 주어진다고 해도 충분히 해결 가능한 시간복잡도임을 알 수 있다.

다만 해당 값을 얻는 최소 연산을 얻어야 하기 때문에 방문 기록을 알아야 한다는 문제가 있다.
이는 다음 방문 위치를 나타낼 때, 그 값과 여태 사용한 연산을 같이 나타내어 해결할 수 있다.

풀이

기본적인 아이디어는 다음과 같다.

각 테스트 케이스에 대해 다익스트라 알고리즘을 사용한다. 이를 위해 다음 방문 위치를 나타내는 큐와 방문 여부를 기록하는 배열을 선언한다.

다음 방문 위치는 D, S, L, R 연산을 각각 수행하여 얻는다.

연산 기록을 얻기 위해 여태 수행한 연산도 다음 방문 위치에 함께 넣는다.

시간 소모를 최소화하기 위해 현재 node에서 도착점과 같은 지를 비교하지 않고, 다음 방문 위치를 얻으면서 동시에 도착점을 비교하였다.

이를 구현한 코드는 다음과 같다.

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

public class Main {
	
	// D 연산
	public static int opD(int input) {
		int output = input * 2;
		
		// 2배한 결과가 9999를 넘으면 10000으로 나눈 나머지 반환
		if (output > 9999) output %= 10000;
		
		return output;
	}
	
	// S 연산
	public static int opS(int input) {
		int output = input - 1;
		
		// 1을 뺀 결과가 -1이라면 9999를 반환
		if (output == -1) output = 9999;
		
		return output;
	}
	
	// L 연산
	public static int opL(int input) {
		int d1 = input / 1000;
		int d2 = (input % 1000) / 100;
		int d3 = (input % 100) / 10;
		int d4 = input % 10;
		
		// 왼쪽으로 회전
		int output = d2 * 1000 + d3 * 100 + d4 * 10 + d1;
		return output;
	}
	
	// R 연산
	public static int opR(int input) {
		int d1 = input / 1000;
		int d2 = (input % 1000) / 100;
		int d3 = (input % 100) / 10;
		int d4 = input % 10;
		
		// 오른쪽으로 회전
		int output = d4 * 1000 + d1 * 100 + d2 * 10 + d3;
		return output;
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder answer = new StringBuilder();
		
		// 테스트 케이스 수 입력 받기
		int T = Integer.parseInt(br.readLine());
		
		// 각 테스트 케이스에 대해 진행
		for (int tc = 0; tc < T; tc++) {
			// 입력 받기
			StringTokenizer stT = new StringTokenizer(br.readLine());

			int A = Integer.parseInt(stT.nextToken());
			int B = Integer.parseInt(stT.nextToken());
			
			// BFS 수행을 위한 선언
			ArrayDeque<String[]> queue = new ArrayDeque<>();
			boolean[] isVisited = new boolean[10000];
			for (int i = 0; i < 10000; i++) {
				isVisited[i] = false;
			}
			
			String[] start = {Integer.toString(A), ""}; // 시작점
			queue.add(start);
			isVisited[A] = true;
			
			// BFS 수행
			while(true) {
				String[] now = queue.poll();
				
				int nowValue = Integer.parseInt(now[0]);
				
				// 각 연산 확인 및 기록
				int nextD = opD(nowValue);
				if (nextD == B) {
					answer.append(now[1]+"D");
					answer.append("\n");
					break;
				}
				
				int nextS = opS(nowValue);
				if (nextS == B) {
					answer.append(now[1]+"S");
					answer.append("\n");
					break;
				}
				
				int nextL = opL(nowValue);
				if (nextL == B) {
					answer.append(now[1]+"L");
					answer.append("\n");
					break;
				}
					
				int nextR = opR(nowValue);
				if (nextR == B) {
					answer.append(now[1]+"R");
					answer.append("\n");
					break;
				}
				
				String[] nextDs = {Integer.toString(nextD), now[1]+"D"};
				if (!isVisited[nextD]) {
					isVisited[nextD] = true;
					queue.add(nextDs);
				}
				
				String[] nextSs = {Integer.toString(nextS), now[1]+"S"};
				if (!isVisited[nextS]) {
					isVisited[nextS] = true;
					queue.add(nextSs);
				}
				
				String[] nextLs = {Integer.toString(nextL), now[1]+"L"};
				if (!isVisited[nextL]) {
					isVisited[nextL] = true;
					queue.add(nextLs);
				}
				
				String[] nextRs = {Integer.toString(nextR), now[1]+"R"};
				if (!isVisited[nextR]) {
					isVisited[nextR] = true;
					queue.add(nextRs);
				}
			}
		}
		
		// 정답 출력
		System.out.println(answer);
	}
}

회고

처음에는 다익스트라 알고리즘이라는 생각을 하지 않고 단순히 BFS로 생각해서 메모리 초과가 계속 발생했었다.
가능한 노드가 1만 개 밖에 안 되는데, 20억 방문할 생각을 했으니.... 큰 착각이었다. 그냥 방문 여부만 기록하면 되는 것이었다.

방문 여부를 기록하지 않은 상황에서 메모리 초과를 해결하기 위해 아주 다양한 시도를 했었다.

방문 기록없는 BFS
https://www.acmicpc.net/source/85105114
StringBuilder 대신 단순 +를 사용해 다음 연산 기록 얻기
https://www.acmicpc.net/source/85105467
목표 값과의 비교를 now가 아니라 next에서 미리 수행하기. 그러면 1/4로 시간과 공간이 감소함
https://www.acmicpc.net/source/85106300
String 배열을 사용해 연산 기록을 얻지 않고, 연산 횟수를 count하고 처음 가능한 연산을 확인하면 그 때의 count를 4로 나눠가면서 여태 수행한 연산을 역추적하기
https://www.acmicpc.net/source/85107333
BFS 시에 사용하는 queue를 재사용해서 이전 테스트 케이스의 큐에 메모리가 남아있지 않도록 하기
https://www.acmicpc.net/source/85107733

마침내 방문 여부를 기록한다는 생각을 해서 해결할 수 있었다....
그러고도 한 번 틀린 이유: 다음 방문 위치를 기록할 때 방문 여부를 갱신하지 않았음

그런데 다른 분들 풀이를 보니 내 풀이의 시간복잡도가 너무 커서 개선을 시도했다.

String 배열 사용해서 다음 방문 위치 얻기(8072 ms)
https://www.acmicpc.net/source/85110151
String 배열 선언을 방문 여부 확인 후 방문하지 않았을 때만 하도록 함(5488 ms)
https://www.acmicpc.net/source/85111013
새로운 클래스인 Node를 선언해서 Integer.toSting()과 Integer.parseInt()를 사용하지 않도록 함(3580 ms)
https://www.acmicpc.net/source/85110833

위의 풀이에 올린 코드는 가장 처음에 해결한 첫번째 풀이이다.
최종 버전은 다음과 같다.

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

public class Main {
	public static class Node {
		int num;
		String ops;
		
		Node(int num, String ops) {
			this.num = num;
			this.ops = ops;
		}
	}
	
	// D 연산
	public static int opD(int input) {
		int output = input * 2;
		
		// 2배한 결과가 9999를 넘으면 10000으로 나눈 나머지 반환
		if (output > 9999) output %= 10000;
		
		return output;
	}
	
	// S 연산
	public static int opS(int input) {
		int output = input - 1;
		
		// 1을 뺀 결과가 -1이라면 9999를 반환
		if (output == -1) output = 9999;
		
		return output;
	}
	
	// L 연산
	public static int opL(int input) {
		int d1 = input / 1000;
		int d2 = (input % 1000) / 100;
		int d3 = (input % 100) / 10;
		int d4 = input % 10;
		
		// 왼쪽으로 회전
		int output = d2 * 1000 + d3 * 100 + d4 * 10 + d1;
		return output;
	}
	
	// R 연산
	public static int opR(int input) {
		int d1 = input / 1000;
		int d2 = (input % 1000) / 100;
		int d3 = (input % 100) / 10;
		int d4 = input % 10;
		
		// 오른쪽으로 회전
		int output = d4 * 1000 + d1 * 100 + d2 * 10 + d3;
		return output;
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder answer = new StringBuilder();
		
		// 테스트 케이스 수 입력 받기
		int T = Integer.parseInt(br.readLine());
		
		// 각 테스트 케이스에 대해 진행
		for (int tc = 0; tc < T; tc++) {
			// 입력 받기
			StringTokenizer stT = new StringTokenizer(br.readLine());

			int A = Integer.parseInt(stT.nextToken());
			int B = Integer.parseInt(stT.nextToken());
			
			// BFS 수행을 위한 선언
			ArrayDeque<Node> queue = new ArrayDeque<>();
			boolean[] isVisited = new boolean[10000];
			for (int i = 0; i < 10000; i++) {
				isVisited[i] = false;
			}
			
			Node start = new Node(A, ""); // 시작점
			queue.add(start);
			isVisited[A] = true;
			
			// BFS 수행
			while(!queue.isEmpty()) {
				Node now = queue.poll();
				
				// 각 연산 수행 시 정답에 도달하는지 확인
				int nextD = opD(now.num);
				if (nextD == B) {
					answer.append(now.ops+"D");
					answer.append("\n");
					break;
				}
				
				int nextS = opS(now.num);
				if (nextS == B) {
					answer.append(now.ops+"S");
					answer.append("\n");
					break;
				}
				
				int nextL = opL(now.num);
				if (nextL == B) {
					answer.append(now.ops+"L");
					answer.append("\n");
					break;
				}
					
				int nextR = opR(now.num);
				if (nextR == B) {
					answer.append(now.ops+"R");
					answer.append("\n");
					break;
				}
				
				// 연산 결과를 queue에 추가
				if (!isVisited[nextD]) {
					Node nextDs = new Node(nextD, now.ops+"D");
					queue.add(nextDs);
					isVisited[nextD] = true;
				}
				
				if (!isVisited[nextS]) {
					Node nextSs = new Node(nextS, now.ops+"S");
					queue.add(nextSs);
					isVisited[nextS] = true;
				}
				
				if (!isVisited[nextL]) {
					Node nextLs = new Node(nextL, now.ops+"L");
					queue.add(nextLs);
					isVisited[nextL] = true;
				}
				
				if (!isVisited[nextR]) {
					Node nextRs = new Node(nextR, now.ops+"R");
					queue.add(nextRs);
					isVisited[nextR] = true;
				}
			}
		}
		
		// 정답 출력
		System.out.println(answer);
	}
}

박찬병

이전 포스트

[프로그래머스/MySQL] SQL 고득점 Kit 총정리 - SUM, MAX, MIN

다음 포스트

[백준/Java] 9019 DSLR

Problem Solving

문제 요약

문제 접근

풀이

회고

[프로그래머스/MySQL] SQL 고득점 Kit 총정리 - SUM, MAX, MIN

[백준/Java] 7662 이중 우선순위 큐

0개의 댓글