yhb0730   2년 전

숨바꼭질 문제에서 계속해서 시간초과가 떠서 가지치기 방식을 하나 씩 추가하는 방식으로 여러개를 제출해봤는데 전부 시간초과가 걸렸습니다.

 기본적인 방식은 BFS로 했고 사용한 가지치기 방식은

1. 시작할때 대충 bestTime을 구하고 테스트를 하면서 bestTime을 갱신하여 이 시간보다 늦은 경우는 전부 가지치기를 하기. 

2. 현재 도착한 지점이 처음 도착한 경우 시간을 저장하고 다른 케이스에서 해당 지점에 다시 도착하면 시간을 비교해 더 늦은 시간에 도착한 경우 가지치기.  

3. 곱셈으로 이동하는 경우 제한을 둬서 해당 거리 이상은 못 움직이게 하기

4. 동생이 자기보다 뒤에 있는 경우 1칸씩 뒤로가서 도착하는 경우밖에 없으니 일일히 가보지 말고 바로 뺄셈 써서 이동하기

이 정도 입니다. 가지치기 방식이 늘어난다고 시간이 빨라지지 않는다고 해서 이리저리 조합해봐서 써보고 한번에 다 써보기도 했는데 계속해서 시간초과가 뜨네요. 혹시 무한루프가 걸린게 아닐까해서 랜덤 테스트 케이스도 해봤는데 찾기가 힘듭니다. 어디가 문제일까요? 

djm03178   2년 전

굉장히 어렵게 구현하신 것 같은데, 가지치기를 하더라도 DFS를 써서는 시간 내에 통과하기는 어려울 거라 생각되네요.

'최단거리' 문제는 DFS에 적합하지 않습니다. BFS를 사용하셔야 합니다.

yhb0730   2년 전

아 죄송합니다 BFS를 쓴게 맞습니다. DFS로 처음에 만들었다가 스택 오버플로우 나서 바꿨거든요. 질문을 잘못 적었습니다

djm03178   2년 전

BFS라면 중복 방문이 일어나지 않도록 처리를 해줘야 됩니다. 이미 방문한 점을 계속 큐에 넣으면 그만큼 시간이 아주 많이 늘어납니다.

yhb0730   2년 전

답변 감사합니다. 그런데  죄송한데 제 코드 중 int &before = cache[dis]; 가 중복 방문을 체크하는 코드라고 생각했었는데  잘못 생각한걸까요? 

이번에 if(before != -1) continue; 로 제출해서 확인해봤는데도 똑같은 지점에서 계속 걸립니다.

djm03178   2년 전

지금 제가 이 코드를 잘 이해하지 못하겠는데요, 일단 BFS면 무조건 시간 순서대로 방문하니까 가지치기라는 것 자체가 필요 없지 않나요?

그리고, BFS는 큐에서 뺀 다음에 중복검사를 하는 게 아니라 큐에 넣을 때 중복검사를 해야 중복방문이 일어나지 않습니다.

yhb0730   2년 전

아 제가 DFS에서 BFS에서 바꾸면서 생각을 잘못 했던거 같습니다. 그리고 큐에 넣을 때 중복검사를 해야된다는걸 몰랐네요. 한번 참조해서 해봐야겠습니다. 답변 감사합니다.

yhb0730   2년 전

해결됬습니다. 간단한 문제였는데 잘못 알고있어서 질질 끌었네요. 감사합니다

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