ast3138   9달 전

0,0에서 부터 상하좌우로 bfs를 진행합니다. 방문표시로 key의 개수를 넣어 줘서 key값이 같으면 재방문을 못하게 합니다.

'$'은 99999란 수를 넣어서 한번 방문시 다시 방문하지 못하게 합니다.

그러다가 새로운 key를 주우면 큐를 초기화하고 key+1를 한채로 새로운 bfs를 진행합니다. 

테스트 케이스는 다 통과하구요 50%에서 시간초과가 납니다.

어떤 부분이 비효율적인지랑... 혹시 해결책을 주시면 정말 감사하겠습니다.

imn00133   9달 전

제가 java를 다루지 않아서 코드를 읽지 않았지만, 키를 찾을 때마다 bfs를 다시 돌리는 것은 너무 느릴 것 같습니다.

대충 최악의 경우를 보면 26번 bfs를 돌리게 됩니다.

키를 찾을 때 마다 bfs를 다시 돌리지 않고, 키를 찾았을 때 문을 어떻게 열지 생각해보시는 쪽이 좋을 것 같습니다.

ast3138   9달 전

답변주셔서 정말 감사합니다. 제가 생각하기에 최악의 경우가 26번이면 4(상하좌우)*(102*102)(배열의 크기)*26(bfs횟수) -> 4*102^2*26으로 백만정도가 나오게 되는데

충분히 가능한 시간이라고 생각합니다. 혹시 최악의 경우가 26번일 경우에 대해서 좀더 설명 해주실수 있을까요?

ast3138   9달 전

아...key가 알파벳이니깐 26개가 되는군요.. 감사합니다...

imn00133   9달 전

@ast3138

간단하게 생각해서 26번이긴 했는데, key가 26개 이상 주어질 수도 있긴 합니다. 이미 받은 부분에 대한 예외처리는 하셨나요?

1회에 테스트 케이스는 100개가 넘지 않으니 최악의 경우 1억이 약간 왔다갔다하네요.

imn00133   9달 전

@ast3138

50%이면 제가 틀렸던 부분과 유사한데, 살펴보니 $에 재방문이 불가하게 처리되네요.

$를 획득한 이후 그 이후 위치에 대해서 탐색이 가능한가요?

ast3138   9달 전

$에 대한 부분은 방문시 '.'으로 처리를 해서 한번 방문하면 다시 방문해도 아무일 없게 했습니다.

결국 50%%에서 계속 시간초과가 나서 다른분의 코드를 참고하게 됬네요 ㅠ

다른 분의 코드를 보니 제가 생각하는 방법이 너무 많은 탐색을 하다는 것을 깨달았습니다.  bfs가 너무 많이 실행되는 것을 한눈에 볼수있었습니다.

imn0133님 덕분에 로직에 대해 틀린 부분은 없지만 (있을수도 있지만)  상당히 비효율적인 것은 확실히 알았습니다. 감사합니다!

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