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

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

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

               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)));

}

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