[Baekjoon] 9019_DSLR

Gold IV

문제(출처: https://www.acmicpc.net/problem/9019)

---

< DSLR >

 

문제 풀이

 

bfs를 활용하여 D S L R 명령어를 실행한다. 그 결과가 B가 되었다면 바로 종료해 준다.

결과가 B가 아니라면 계속해서 queue에 넣어주며 결과가 나올 때까지 실행해 준다.

 

 

 - my solution (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class _9019_ {
	static int A,B;
	static String result="";
	static Queue<Integer>queue;
	static Queue<String>cmd;
	static boolean check[];

	public static void main(String[] args) throws IOException {
		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int T=Integer.parseInt(bf.readLine()); //테스트 케이스
		queue=new LinkedList<>();
		cmd=new LinkedList<>();
		
		for(int i=0; i<T; i++) {
			st=new StringTokenizer(bf.readLine());
			A=Integer.parseInt(st.nextToken());
			B=Integer.parseInt(st.nextToken());
			result="";
			queue.clear();
			cmd.clear();
			check=new boolean[10000];
			search();
			System.out.println(result);
		}
	}
	private static int D(int num) {
		return (num*2)%10000;
	}
	
	private static int S(int num) {
		if(num==0) return 9999;
		else return num-1;
	}
	
	private static int L(int num) { 
		int n=num%1000;
		int temp=num/1000;
		return (n*10)+temp;
	}
	
	private static int R(int num) {
		int n=num/10;
		int temp=num%10;
		return (temp*1000)+n;
	}

	private static void search() {
		queue.add(A);
		check[A]=true;
		cmd.add("");
		
		while(!queue.isEmpty()) {
			int n=queue.poll();
			String line=cmd.poll();

			int num=D(n);
			if(num==B) {
				result=line+"D";
				break;
			}
			else if(!check[num]){
				check[num]=true;
				queue.add(num);
				cmd.add(line+"D");
			}
			num=S(n);
			if(num==B) {
				result=line+"S";
				break;
			}
			else if(!check[num]){
				check[num]=true;
				queue.add(num);
				cmd.add(line+"S");
			}

			num=L(n);
			if(num==B) {
				result=line+"L";
				break;
			}
			else if(!check[num]){
				check[num]=true;
				queue.add(num);
				cmd.add(line+"L");
			}
			num=R(n);
			if(num==B) {
				result=line+"R";
				break;
			}
			else if(!check[num]){
				check[num]=true;
				queue.add(num);
				cmd.add(line+"R");
			}
			if(result!="")break;
		}
	}
}

 

• Main
  • queue: 레지스터의 값 저장
  • cmd: 현제까지 실행한 명령어
  • check: 레지스터 중복 확인
• D : 2배로 바꾼 후 10000으로 나눈 나머지를 반환
• S : 레지스터 값이 0 이면 9999 반환 , 0이 아니면 1 뺀 값을 반환
• L : 자릿수를 왼편으로 회전시키는 방법은 몫 연산을 통해 첫째 자리를 저장, 나머지 연산을 통해 세 자리를 저장한 후 세 자리*10을 한 후 몫을 더해준다. (세 자리*10을 하면 4자리로 맞춰지기 때문이다)
• R : 자릿수를 오른편으로 회전시키는 방법은 몫 연산을 통해 세 자리를 저장, 나머지 연산을 통해 마지막자리를 저장한 후 마지막 자리를 첫 번째 자리로 만들기 위해 1000을 곱한 후 나머지 세 자리를 더해준다.
• search
  • queue, check, cmd에 초기값을 넣어준다
  • queue가 빌 때까지 반복 -> 각 queue에서 하나씩 뽑은 후 연산을 수행해 준다. D, S, L, R 명령을 실행 후 그 값이 B와 같다면 종료해 준다. B와 같지 않다면 중복된 레지스터 값인지 확인 후 중복된 값이 아니라면 중복 check, queue, cmd에 넣어준다.

---

생각🤔

 

힘들었다!!!

 

처음에는 R와 L 연산 때문에 int로 받은 값을 string으로 바꿔주었으며, 중복 check를 위해 hashset을 사용했었다. 하지만 계속해서 시간 초과와 메모리 초과가 발생하였다. 여기서 큰 이유는 int를 string으로 계속해서 바꿔주는 연산 때문에 시간초과가 발생한다고 생각하였다. 그래서 조금 힌트를 얻고 생각해본 결과 L과 R을 int인 상태에서 해결할 수 있었다.

 

그 후에는 메모리 초과가 문제였다. 이 부분은 잘 몰라서 찾아보니 queue 초기화와 중복 check 때문인 것 같았다. 그래서 queue를 clear를 해주었으며, 레지스터 값이 0 이상 10000 미만으로 정해져 있으므로 배열을 통해 중복 확인을 해주는 것으로 코드를 수정하였다. 그 결과 통과할 수 있었다.

 

---