songgj123   2년 전

DP로 풀었더니 시간 초과가 나서

BFS로 다시 풀었는데 또 시간 초과가 나오네요


기본적인 BFS와 같습니다.

첫 줄을 탐색하며 1이 있는 지점을 찾아 출발합니다.

한 번의 출발에서 다시 방문하지 않도록, visited 배열을 선언해 걸음 수를 저장했습니다.


다음 출발 때도 visited 배열은 계속 유지해서

다음 출발 이후에 그 지점을 방문했을 때, 걸음 수와 visited 배열을 비교해 지점을 queue에 저장할지 정합니다.


더 줄일 방법이 생각이 안나서 그러는데 어떤 식으로 시간을 줄일 수 있을까요??

한 가지 생각해 본 것은 어떤 path가 조건에 맞지 않으면,

path 내의 지점들을 다음부터 방문하지 않도록 하는 방법입니다.


조언해주시면 감사하겠습니다.

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