ainch96   8년 전

알고리즘을 설명 하자면 bfs로 탐색을 하려고 했습니다.

각 상태를 하나의 int 형으로 표시 했습니다.

1 2 3

4 5 6

7 8 0   은 123456780 이런 식으로요.

그리고 두개의 함수를 만들었습니다. compl은 답에 도달 했는지를 확인해 주는 함수입니다.

next_p 는 어떤 특정 퍼즐 상태와 0을 움직일 방향을 (상,하,좌,우 = 0,1,2,3)을 인수로 해서 다음 퍼즐 상태를 반환해 주는 함수 입니다.

이 두 함수를 이용해서 bfs를 구현했습니다. queue에 삽입 하는 값은(거리, 상태 정수)를 넣고,

답이 나올 때 까지 혹은 queue 가 빌 때 까지 진행했습니다.

방문 상태 인지를 확인 하는 방법은 map을 이용해서 map < int , int > visi를 한 후

visi[876543210] = 1같이 했습니다.


저는 이 방법을 v : 9! 이고 정점에 연결 된 간선은 최대 4개 니까 e : 4*9 으로 해서

O(5*9!)으로 보았고, 그리고 map 삽입하는 시간은 O(log9!) 으로 계산해서

총 O(5*9!*log(9!))으로 ==  3*10^7 정도로 계산했습니다.


그런데 시간이 너무 오래 걸립니다.  

혹시 map 의 시간복잡도가 logarithm이 아닌가요?

만약 아니라면 다른 자료구조를 써서라도 시간을 줄일 수 있는 방법이 존재 할까요?

도와주세요 고수님들 ㅠㅠㅠ

koosaga   8년 전

그냥 좀 느린거 같아요.


잡다구리한 최적화가 도움이 되지 않을까요?

(할만한 최적화는, cur_state를 큐에서 빼자 마자 크기를 압축하고, next[][] 배열을 처음에 precompute해서 다시 계산하지 않게 하는 것 정도가 있겟네요.)

koosaga   8년 전

압축한다는 게 설명이 애매한데 모든 가능한 상태를 map에 넣고 크기를 0 ~ 9!-1 사이의 정수로 표현하는 방식을 말한거에요

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