[backjoon]9019 DSLR java

www.acmicpc.net/problem/9019

9019번: DSLR

1. BFS로 풀이

2. 주어진 사항에 맞게 풀이하면 금방 풀 수 있음.

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

class Main {
	static boolean[] visit = new boolean[10000];
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		int testCase = Integer.parseInt(st.nextToken());
		
		for (int i = 0; i < testCase; i++) {
			st = new StringTokenizer(br.readLine());
			int cur = Integer.parseInt(st.nextToken());
			int target = Integer.parseInt(st.nextToken());
			
			bfs(target, cur);
		}
	}
	
	
	public static void bfs(int target, int init) {
		boolean[] visit = new boolean[10000];
		StringBuffer sb;
		int temp;
		Queue<Node> queue = new LinkedList<Node>();
		
		queue.add(new Node(init, ""));
		
		while(!queue.isEmpty()) {
			Node cur = queue.poll();
			if(cur.number == target) {
				System.out.println(cur.str);
				break;
			}
			//D
			sb= new StringBuffer();
			sb.append(cur.str);
            
			temp = cur.number;
			temp*=2;
			if(temp >= 10000) temp %=10000;
            
			if(!visit[temp]) {
				queue.add(new Node(temp, sb.append("D").toString()));
				visit[temp] = true;
			}
			
			//S
			sb= new StringBuffer();
			sb.append(cur.str);
            
			temp = cur.number;
			temp-=1;
			if(cur.number == 0) temp =9999;
            
			if(!visit[temp]) {
				queue.add(new Node(temp, sb.append("S").toString()));
				visit[temp] = true;
			}
			//L
			sb= new StringBuffer();
			sb.append(cur.str);
            
			temp = (cur.number%1000)*10 +(cur.number/1000);
			
            if(!visit[temp]) {
				queue.add(new Node(temp, sb.append("L").toString()));
				visit[temp] = true;
			}
			//R
			sb= new StringBuffer();
			sb.append(cur.str);
			
            temp = (cur.number%10)*1000 +(cur.number/10);
			
            if(!visit[temp]) {
				queue.add(new Node(temp, sb.append("R").toString()));
				visit[temp] = true;
			}
		}
	}
	
}
class Node{
	int number;
	String str;
	
	Node(int number, String str){
		this.number = number;
		this.str = str;
	}
}

 

 

이 문제를 풀면서 bfs에 굉장히 안일했음을 깨달았다.

1. 수학을 다짜고짜 멀리하려함.

2. 최단거리는 bfs라 생각하자 했지만, 1차원 형태라 생각하여 dfs로 돌림

3. 테스트 케이스가 여러 개였는데 visit 초기화를 제대로 안 함.

4. 마음만 급해서 중복 코드가 많다 ㅜㅜ