글 읽기 - 시간초과 해결법!

barcelonamessi 7년 전 0

bfs를 사용해서 node에 해당하는 정보(현재 값, 현재까지의 DSLR정보(BigInteger))를 갱신하면서 먼저 답이 오면 출력하는 방식으로 풀었습니다.

또한 visit이라는 배열을 사용하여 방문을 이미 했다면 더이상 가지 않도록 구현을 하였습니다.

그런데 계속 시간초과가 나서 질문드립니다. 힌트좀 주시면 감사하겠습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
	static class Node{
		int value;
		BigInteger str;
		Node(){}
		Node(int value, BigInteger str){
			this.value=value;
			this.str=str;
		}
	}
	

	public static void main(String[] args) throws IOException{
		BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer token=new StringTokenizer(in.readLine());
		
		
		int T;
		
		T=Integer.parseInt(token.nextToken());
		
		for(int i=0; i<T; i++){
			token=new StringTokenizer(in.readLine());
			int from=Integer.parseInt(token.nextToken());
			int to=Integer.parseInt(token.nextToken());
			LinkedList<Node> list=new LinkedList<Node>();
			BigInteger result=BigInteger.ZERO;
			int[] visit=new int[10000];
			//D-> 2배하고 10000으로 나눈 나머지
			//S-> 1 마이너스
			//L-> 왼쪽으로 이동
			//R-> 오른쪽으로 이동
			list.add(new Node(from, BigInteger.ZERO));
			while(!list.isEmpty()){
				Node cur=list.peek();
				list.remove();
				int temp=cur.value;
				if(cur.value==to){
					result=cur.str;
					break;
				}
				if(visit[cur.value]==1)
					continue;
				visit[cur.value]=1;
				int D=cur.value*2%10000;
				int S=cur.value-1;
				if(S==-1)
					S=9999;
				int L=cur.value/1000+cur.value/100%10*1000+cur.value/10%10*100+cur.value%10*10;
				int R=cur.value/1000*100+cur.value/100%10*10+cur.value/10%10+cur.value%10*1000;
                if(D==to){
                    result=cur.str.multiply(BigInteger.TEN).add(BigInteger.ONE);
                    break;
                }
                if(S==to){
                    result=cur.str.multiply(BigInteger.TEN).add(BigInteger.valueOf(2));
                    break;
                }
                if(L==to){
                    result=cur.str.multiply(BigInteger.TEN).add(BigInteger.valueOf(3));
                                                                break;
                }
                if(R==to){
                    result=cur.str.multiply(BigInteger.TEN).add(BigInteger.valueOf(4));
                                                                break;
                }                                                                
				
				//D==1 S==2 L ==3 R ==4
				//System.out.println(D+ " , " + S + " , " + L + " , " + R);
				
				if(visit[D]==0)
					list.add(new Node(D, cur.str.multiply(BigInteger.TEN).add(BigInteger.ONE)));
				if(visit[S]==0)
					list.add(new Node(S, cur.str.multiply(BigInteger.TEN).add(BigInteger.valueOf(2))));
				if(visit[L]==0)
					list.add(new Node(L, cur.str.multiply(BigInteger.TEN).add(BigInteger.valueOf(3))));
				if(visit[R]==0)
					list.add(new Node(R, cur.str.multiply(BigInteger.TEN).add(BigInteger.valueOf(4))));
				
				
				
			}
			int power=0;
			BigInteger temp=result;
			//System.out.println(result);
			while(temp.compareTo(BigInteger.ZERO)>0){
				temp=temp.divide(BigInteger.TEN);
				
				power++;
			}
			
			for(int k=0; k<power; k++){
				int ch=result.divide(BigInteger.valueOf((int)Math.pow(10, power-k-1))).intValue();
				//result-=
						
				result=result.subtract(result.divide(BigInteger.valueOf((int)Math.pow(10, power-k-1))).multiply(BigInteger.valueOf((int)Math.pow(10, power-k-1))));
					//	result/(int)Math.pow(10, power-k-1)*(int)Math.pow(10, power-k-1);
				if(ch==1)
					System.out.print("D");
				else if(ch==2)
					System.out.print("S");
				else if(ch==3)
					System.out.print("L");
				else if(ch==4)
					System.out.print("R");
			}
			System.out.println();
			
			
		}
		

	}

}

if(visit[D]==0)
                    list.add(new Node(D, cur.str.multiply(BigInteger.TEN).add(BigInteger.ONE)));
                if(visit[S]==0)
                    list.add(new Node(S, cur.str.multiply(BigInteger.TEN).add(BigInteger.valueOf(2))));
                if(visit[L]==0)
                    list.add(new Node(L, cur.str.multiply(BigInteger.TEN).add(BigInteger.valueOf(3))));
                if(visit[R]==0)
                    list.add(new Node(R, cur.str.multiply(BigInteger.TEN).add(BigInteger.valueOf(4))));

이부분에서

1.다음 방문을 할 숫자가 방문 하지 않았다면 리스트에 추가하고

2. 새로이 리스트에서 노드를 받아서 현재 노드를 방문하였다고 표시하였는데

이것이 다음에 방문을 할 것을 저장 안해서 같은 노드가 여러번 추가될 가능성을 발견하였습니다.

ex) 1111 과 같은경우 L,R값이 같은데 L에서 추가하고 R에서도 추가합니다.

그래서 리스트에 추가하기 전에 미리 다음 방문할 지점을 방문한다고 표시를 해주었더니 시간 내에 통과가 되었습니다.

if(visit[D]==0) {

visit[D]=1;//<-----------------------이부분

list.add(new Node(D, cur.str.multiply(BigInteger.TEN).add(BigInteger.ONE)));

}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과 해결법!

barcelonamessi 7년 전 0

barcelonamessi 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말