mincoln419   3년 전

BFS 로 풀게 되면 pypy 로 정상적으로 통과되는데 python3로 하면 성능이 느리다 보니 시간초과 걸릴 수 있습니다.

특히 최대거리가 가장 많은 케이스일 경우 = 모든 지역이 'L' 인경우인데 이 경우의 정답은 len(X) +len(Y) - 2 입니다

만약에 탐색을 하다가 최대거리가 이미 나온 경우에는 또다시 탐색할 필요가 없어집니다.

결국 이러한 경우에 loop 를 중단하게 되면 시간 초과 문제가 사라지게 됩니다.

만약에 W가 있어서 삥 돌아가는 케이스가 있다면 그 경우의 수가 줄게 되어서 시간초과되는 케이스가 발생하지 않습니다.

 

choongyul   2년 전

감사합니다.

테스트 케이스가 55%일 때, 딱 그런 케이스 인 것 같네요.

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