artage7   2년 전

일단 맞췄긴 했는데

시간이 무려 5400ms 나 나옵니다..; 푸신거 보니깐 740ms 도 나오던데 차이가 너무 심해서

살펴보니깐 경로를 배열로 출력하는거 같은데 이해가 잘 안되더라구요... ( 사고가 막힌느낌 ..;)


제 알고리즘은 BFS인데  큐에 저장하는 정보를 구조체로 정의했습니다.

구조체에는 DSLR 계산한 숫자와  각각의 BFS 노드마다 지나온 경로를 저장하기 위한 trace 벡터를 저장합니다.

그러니깐  모든 노드에는 계산한 값과 그 노드가 어떤 경로로 오게됬는지 알기 위한 배열을 가집니다.

   1

2 3 4 

1에서 2, 3, 4 노드를 BFS알고리즘에 따라 집어 넣으면

2번 노드 경로는 1,2

3번 노드 경로는 1,3

4번 노드 경로는 1,4

가 저장되고... 이런식으로 각각 자기 부모로 부터 얻은 위치에 자기 위치를 추가해서 저장하는... 식으로요..


BFS나 DFS 풀때마다 경로 출력하는 문제를 접하게 되는데

항상 이런식으로 풀다보니깐 메모리와 시간이 후달려서 질문드립니다.



kdk8361   2년 전

값으로 나올 수 있는게 결국 0~9999니까 10000짜리 배열 만들어놓고 BFS 돌리면서 온 길을 저장하는 방식을 사용하니 1152ms 나오네요.
x = 1234
nx = 2341일 때
f[nx] = x
이렇게 저장했습니다.

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