https://www.acmicpc.net/problem/9019
처음에 시간초과가 났던 문제이다.
첫시도 코드(통과는 함)
import java.io.*;
import java.util.*;
public class Main
{
static int r;
static int c;
public static int DSLR(int number,int method){
if(method==0){
return (number*2)%10000;
}
if(method==1){
return number==0?9999:number-1;
}
if(method==2){
int first = number/1000;
int second = (number%1000)/100;
int third = (number%100)/10;
int fourth = number%10;
return second*1000 + third*100 + fourth*10 + first;
}
if(method==3){
int first = number/1000;
int second = (number%1000)/100;
int third = (number%100)/10;
int fourth = number%10;
return fourth*1000 + first*100 + second*10 + third;
}
return 0;
}
public static String bfs(int a, int b){
Queue<Node> q = new LinkedList();
boolean[] visited = new boolean[10001];
String[] move = {"D","S","L","R"};
Node start = new Node(a,"");
q.offer(start);
while(q.size()>0){
Node node = q.poll();
if(node.number==b){
return node.path;
}
visited[node.number] = true;
for(int i=0; i<4;i++){
Node next = new Node(DSLR(node.number,i),node.path+move[i]);
if(!visited[next.number]){
q.offer(next);
//이 부분을 빼먹어서(잘못적어서) 시간초과가 났음;;
visited[next.number] = true;
}
}
}
return "";
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t= Integer.parseInt(br.readLine());
while(t-->0){
String[] input1 = br.readLine().split(" ");
int a = Integer.parseInt(input1[0]);
int b = Integer.parseInt(input1[1]);
System.out.println(bfs(a,b));
}
}
public static class Node{
int number;
String path;
public Node(int number, String path){
this.number = number;
this.path = path;
}
}
}
인스턴스마다 경로를 들고 있는 것이 무겁다고 생각해
숫자범위만큼의 스트링 배열을 만들고 저장 시켜주었다.
import java.io.*;
import java.util.*;
public class Main
{
public static int DSLR(int number,int method){
if(method==0){
return (number*2)%10000;
}
if(method==1){
return number==0?9999:number-1;
}
if(method==2){
int first = number/1000;
int second = (number%1000)/100;
int third = (number%100)/10;
int fourth = number%10;
return second*1000 + third*100 + fourth*10 + first;
}
if(method==3){
int first = number/1000;
int second = (number%1000)/100;
int third = (number%100)/10;
int fourth = number%10;
return fourth*1000 + first*100 + second*10 + third;
}
return 0;
}
public static String bfs(int a, int b){
Queue<Integer> q = new LinkedList();
boolean[] visited = new boolean[10000];
String[] route = new String[10000];
String[] move = {"D","S","L","R"};
q.offer(a);
route[a]="";
while(q.size()>0){
int num = q.poll();
if(num==b){
return route[num];
}
visited[num] = true;
for(int i=0; i<4;i++){
int next = DSLR(num,i);
if(!visited[next]){
q.offer(next);
visited[next] = true;
route[next] = route[num]+move[i];
}
}
}
return "";
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t= Integer.parseInt(br.readLine());
while(t-->0){
String[] input1 = br.readLine().split(" ");
int a = Integer.parseInt(input1[0]);
int b = Integer.parseInt(input1[1]);
System.out.println(bfs(a,b));
}
}
}
예제 코드 (스트링 빌더 이용)
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int tc = sc.nextInt();
for (int t = 0; t < tc; t++) {
int in = sc.nextInt();
int out = sc.nextInt();
boolean[] check = new boolean[10000];
char[] cmd = {'D', 'S', 'L', 'R'};
Queue<Register> q = new LinkedList<>();
q.add(new Register(in, new StringBuilder()));
check[in] = true;
while (!q.isEmpty()) {
Register now = q.poll();
if (now.num == out) {
System.out.println(now.cmd);
break;
}
int[] next = {now.calcD(), now.calcS(), now.calcL(), now.calcR()};
for (int i = 0; i < 4; i++) {
if (!check[next[i]]) {
check[next[i]] = true;
q.add(new Register(next[i], new StringBuilder(now.cmd).append(cmd[i])));
}
}
}
}
}
}
class Register {
int num;
StringBuilder cmd;
Register(int num, StringBuilder cmd) {
this.num = num;
this.cmd = cmd;
}
public int calcD() {
return (num * 2) % 10000;
}
public int calcS() {
return (num - 1) < 0 ? 9999 : num - 1;
}
public int calcL() {
return (num % 1000) * 10 + num / 1000;
}
public int calcR() {
return (num % 10) * 1000 + num / 10;
}
}
'Problem Solving > BFS' 카테고리의 다른 글
BOJ14442 벽부수고 이동하기2 (0) | 2024.03.12 |
---|---|
벽 부수고 이동하기 (0) | 2024.03.11 |
BOJ5427 불 (0) | 2024.03.11 |
BOJ7569 토마토 (0) | 2024.03.11 |
BOJ7562 나이트의 이동 (0) | 2024.03.10 |