yhs1020   4년 전

뭐가 문제일까요.. queue 사용해서 bfs로 풀었는데 시간초과가 뜹니다.

어느 부분을 줄여야 할까요 어떤부분이 시간을 많이 잡아먹는지..

djm03178   4년 전

BFS할 때 많이 하는 실수인데요, 방문 체크를 큐에서 꺼낸 후에 할 게 아니라, 큐에 추가하는 과정에 해야 됩니다. 안 그러면 중복 방문을 하게 돼요.

예를 들어

11

11

과 같이 되어 있다면, 왼쪽 위에서 시작해서 다음 차례에 오른쪽 위, 왼쪽 아래를 가게 되겠죠. 그런데 각각의 점을 방문할 때 오른쪽 아래에 방문 체크가 안 되어있기 때문에 두 점에서 모두 오른쪽 아래 점을 큐에 넣게 됩니다. 결과적으로 오른쪽 아래 점은 2번 방문하게 됩니다.

yhs1020   4년 전

djm03178님 감사합니다

그걸 생각못했네요!

allen246   10달 전

@djm03178


감사합니다! 가끔씩 BFS할때 어떤건 빠르게 되고 어떤건 느린가 했더니 저걸 무의식적으로 쓰거나 안쓰거나 했었네요!

좋은 팁 알아갑니다 감사합니다! 

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