https://www.acmicpc.net/problem/9019
9019번: DSLR
네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에
www.acmicpc.net
코드설명
BFS 문제입니다.
처음에 DFS를 통해서 진행하려고하였지만, BFS로 바꿔어서 풀었습니다.
문제에서 유의해야할점은, 숫자는 항상 무조건 4자리수라는 것입니다. 문제조건에는 n의 네 자릿수를 d1, d2, d3, d4라고 하자(즉 n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4라고 하자) 이렇게 나와있습니다.
즉, 1도 단순히 1 이 아닌 0001 이라고 생각해야합니다. 그렇기에 이 숫자를 1000 으로 만들면, R 연산 한번을 통하여 1000으로 만들 수 있습니다.
1
1 1000
answer : R처음에 그렇다면 아래의 코드처럼 처리할려고하였으나 그렇게할경우 시간초과가 발생합니다.
String.format("%04d", num);그렇기에 아래의 코드처럼 L 연산과 R연산을 처리한다면 훨씬 빠르게 처리가 가능합니다.
'L'연산 result = ( num % 1000) * 10 + num/1000;
'R'연산 result = ( num % 10) * 1000 + num/10;코드
무조건 4자리수인것이니, 아래와 같은 로직을 통해 가능합니다.
'L'연산 result = ( num % 1000) * 10 + num/1000;
R'연산 result = ( num % 10) * 1000 + num/10;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static int T;
public static int startNum, target;
public static int answer = Integer.MAX_VALUE;
public static boolean[] visited;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
T = Integer.parseInt(st.nextToken());
for(int t=0;t<T;t++) {
st = new StringTokenizer(br.readLine());
startNum = Integer.parseInt(st.nextToken());
target = Integer.parseInt(st.nextToken());
simulate(new Node(startNum, "", 0));
}
}
public static void simulate(Node start) {
Queue<Node> q = new LinkedList<Node>();
visited = new boolean[10000];
visited[start.num] = true;
q.offer(start);
while(!q.isEmpty()) {
Node temp = q.poll();
int num = temp.num;
String operandHistory = temp.operandHistory;
int cnt = temp.cnt;
if(num == target) {
System.out.println(operandHistory);
return ;
}
for(int dir = 0; dir<4; dir++) {
int result;
if(dir == 0) {
//'D'연산
result = ( num * 2 ) % 10000;
if(visited[result] == true) continue;
visited[result] = true;
q.offer(new Node(result, operandHistory + "D", cnt + 1));
}
else if(dir == 1) {
//'S'연산
if( num == 0) { result = 9999; }
else { result = num - 1; }
if(visited[result] == true) continue;
visited[result] = true;
q.offer(new Node(result, operandHistory + "S", cnt + 1));
}
else if(dir == 2) {
//'L'연산
result = ( num % 1000) * 10 + num/1000;
if(visited[result] == true) continue;
visited[result] = true;
q.offer(new Node(result, operandHistory + "L", cnt + 1));
}
else if(dir == 3) {
//'R'연산
result = ( num % 10) * 1000 + num/10;
if(visited[result] == true) continue;
visited[result] = true;
q.offer(new Node(result, operandHistory + "R", cnt + 1));
}
}
}
}
}
class Node{
int num;
String operandHistory;
int cnt;
public Node(int num, String operandHistory, int cnt) {
this.num = num;
this.operandHistory = operandHistory;
this.cnt = cnt;
}
}
n은 4자리수인걸 고려하고 코딩하였으나, String.format("%04d", num); 으로 하니 시간초과가 발생합니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static int T;
public static int startNum, target;
public static int answer = Integer.MAX_VALUE;
public static boolean[] visited;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
T = Integer.parseInt(st.nextToken());
for(int t=0;t<T;t++) {
st = new StringTokenizer(br.readLine());
startNum = Integer.parseInt(st.nextToken());
target = Integer.parseInt(st.nextToken());
simulate(new Node(startNum, "", 0));
}
}
public static void simulate(Node start) {
Queue<Node> q = new LinkedList<Node>();
visited = new boolean[10000];
visited[start.num] = true;
q.offer(start);
while(!q.isEmpty()) {
Node temp = q.poll();
int num = temp.num;
String operandHistory = temp.operandHistory;
int cnt = temp.cnt;
if(num == target) {
System.out.println(operandHistory);
return ;
}
for(int dir = 0; dir<4; dir++) {
int result;
if(dir == 0) {
//'D'연산
result = ( num * 2 ) % 10000;
if(visited[result] == true) continue;
visited[result] = true;
q.offer(new Node(result, operandHistory + "D", cnt + 1));
}
else if(dir == 1) {
//'S'연산
if( num == 0) { result = 9999; }
else { result = num - 1; }
if(visited[result] == true) continue;
visited[result] = true;
q.offer(new Node(result, operandHistory + "S", cnt + 1));
}
else if(dir == 2) {
//'L'연산
String str = String.format("%04d", num);
String newStr = "";
String storeFirstWord = String.valueOf(str.charAt(0));
for(int i=1;i<4;i++) {
newStr += str.charAt(i);
}
newStr += storeFirstWord;
result = Integer.parseInt(newStr);
if(visited[result] == true) continue;
visited[result] = true;
q.offer(new Node(result, operandHistory + "L", cnt + 1));
}
else if(dir == 3) {
//'R'연산
String str = String.format("%04d", num);
String newStr = "";
String storeLastWord = String.valueOf(str.charAt(3));
newStr += storeLastWord;
for(int i=0;i<3;i++) {
newStr += str.charAt(i);
}
result = Integer.parseInt(newStr);
if(visited[result] == true) continue;
visited[result] = true;
q.offer(new Node(result, operandHistory + "R", cnt + 1));
}
}
}
}
}
class Node{
int num;
String operandHistory;
int cnt;
public Node(int num, String operandHistory, int cnt) {
this.num = num;
this.operandHistory = operandHistory;
this.cnt = cnt;
}
}
너비우선 탐색으로 변경하여 진행하였으나, 10 을 'L' 연산을 진행한다고했을떄 '1' 이 되는줄 알았으나 '100' 이 되어야하는점을 고려하지 않았습니다. 무조건 n은 4자리수임을 유의해야합니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static int T;
public static int startNum, target;
public static int answer = Integer.MAX_VALUE;
public static boolean[] visited;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
T = Integer.parseInt(st.nextToken());
for(int t=0;t<T;t++) {
st = new StringTokenizer(br.readLine());
startNum = Integer.parseInt(st.nextToken());
target = Integer.parseInt(st.nextToken());
simulate(new Node(startNum, "", 0));
}
}
public static void simulate(Node start) {
Queue<Node> q = new LinkedList<Node>();
visited = new boolean[10000];
visited[start.num] = true;
q.offer(start);
while(!q.isEmpty()) {
Node temp = q.poll();
int num = temp.num;
String operandHistory = temp.operandHistory;
int cnt = temp.cnt;
if(num == target) {
System.out.println(operandHistory);
return ;
}
for(int dir = 0; dir<4; dir++) {
int result;
if(dir == 0) {
//'D'연산
result = ( num * 2 ) % 10000;
if(visited[result] == true) continue;
visited[result] = true;
q.offer(new Node(result, operandHistory + "D", cnt + 1));
}
else if(dir == 1) {
//'S'연산
if( num == 0) { result = 9999; }
else { result = num - 1; }
if(visited[result] == true) continue;
visited[result] = true;
q.offer(new Node(result, operandHistory + "S", cnt + 1));
}
else if(dir == 2) {
//'L'연산
String str = String.valueOf(num);
String newStr = "";
if(str.length() == 4) {
newStr += String.valueOf(String.valueOf(str.charAt(1))) + String.valueOf(String.valueOf(str.charAt(2))) + String.valueOf(String.valueOf(str.charAt(3)));
newStr += String.valueOf(str.charAt(0));
}
if(str.length() == 3) {
newStr += String.valueOf(str.charAt(1)) + String.valueOf(str.charAt(2));
newStr += String.valueOf(str.charAt(0)) + "0";
}
if(str.length() == 2) {
newStr += String.valueOf(str.charAt(1));
newStr += String.valueOf(str.charAt(0)) +"0"+"0";
}
if(str.length() == 1) {
newStr += String.valueOf(str.charAt(0));
}
if(str.length() == 0) {
newStr += "0";
}
result = Integer.parseInt(newStr);
if(visited[result] == true) continue;
visited[result] = true;
q.offer(new Node(result, operandHistory + "L", cnt + 1));
}
else if(dir == 3) {
//'R'연산
String str = String.valueOf(num);
String newStr = "";
if(str.length() == 4) {
newStr += String.valueOf(str.charAt(3)) + String.valueOf(str.charAt(0)) + String.valueOf(str.charAt(1)) + String.valueOf(str.charAt(2));
}
if(str.length() == 3) {
newStr += String.valueOf(str.charAt(2)) + String.valueOf(str.charAt(0)) + String.valueOf(str.charAt(1));
}
if(str.length() == 2) {
newStr += String.valueOf(str.charAt(1)) + String.valueOf(str.charAt(0));
}
if(str.length() == 1) {
newStr += String.valueOf(str.charAt(0));
}
if(str.length() == 0) {
newStr += "0";
}
result = Integer.parseInt(newStr);
if(visited[result] == true) continue;
visited[result] = true;
q.offer(new Node(result, operandHistory + "R", cnt + 1));
}
}
}
}
}
class Node{
int num;
String operandHistory;
int cnt;
public Node(int num, String operandHistory, int cnt) {
this.num = num;
this.operandHistory = operandHistory;
this.cnt = cnt;
}
}
처음에 DFS로 아예 잘못푼 코드 (무한로프가 발생합니다.)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static int T, N, M;
public static int start, target;
public static int answer = -1;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
T = Integer.parseInt(st.nextToken());
for(int t=0;t<T;t++) {
st = new StringTokenizer(br.readLine());
start = Integer.parseInt(st.nextToken());
target = Integer.parseInt(st.nextToken());
simulate(start, "");
}
}
public static void simulate(int startNum, String s) {
if(startNum == target) {
System.out.println(s);
return ;
}
int result;
System.out.println(s);
//'D'연산
result = ( startNum * 2 ) % 10000;
simulate( result , s + "D" );
//'S'연산
if(startNum == 0) { result = 9999; }
else { result = startNum - 1; }
simulate( result , s + "S" );
//'L'연산
String str = String.valueOf(startNum);
String newStr = "";
if(str.length() == 4) {
newStr += str.charAt(1) + str.charAt(2) + str.charAt(3);
newStr += str.charAt(0);
}
if(str.length() == 3) {
newStr += str.charAt(1) + str.charAt(2);
newStr += str.charAt(0);
}
if(str.length() == 2) {
newStr += str.charAt(1);
newStr += str.charAt(0);
}
if(str.length() == 1) {
newStr += str.charAt(0);
}
result = Integer.parseInt(newStr);
simulate( result , s + "L" );
//'R'연산
str = String.valueOf(startNum);
newStr = "";
if(str.length() == 4) {
newStr += str.charAt(3) + str.charAt(0) + str.charAt(1) + str.charAt(2);
}
if(str.length() == 3) {
newStr += str.charAt(2) + str.charAt(0) + str.charAt(1);
}
if(str.length() == 2) {
newStr += str.charAt(1) + str.charAt(0);
}
if(str.length() == 1) {
newStr += str.charAt(0);
}
result = Integer.parseInt(newStr);
simulate( result , s + "R" );
}
}'알고리즘 > 백준' 카테고리의 다른 글
| [백준] 14442 벽 부수고 이동하기 2 - BFS + 방문처리 JAVA (0) | 2023.09.11 |
|---|---|
| [백준] 12886 돌 그룹 - BFS JAVA (0) | 2023.09.10 |
| [백준] 16948 데스 나이트 - BFS JAVA (0) | 2023.09.08 |
| [백준] 16928 뱀과 사다리 게임 - BFS JAVA (0) | 2023.09.08 |
| [백준] 16198 에너지 모으기 - 백트래킹 JAVA (0) | 2023.09.08 |