BFS가 최적으로 작동하려면 같은 점이 2번 이상 큐에 들어가지 않도록 해주어야 합니다.
출발점부터 어떤 점까지 가는 길을 하나 찾았다면, 그 점까지 가는 다른 길이 더 있더라도
이미 처음에 찾은 길보다 더 길거나 같을 테니 필요가 없죠.
이 말은 어떤 점까지 가는 길을 하나 찾는 "즉시" 그 점은 방문 표시를 해주어야 한다는 뜻이고
"어떤 점까지 길을 찾았다"의 다른 표현은
"그 점의 앞점에서 그 점에 대해 24줄의 if문을 검사해서 True가 나왔다"입니다.
즉 방문 표시는 큐에서 꺼냈을 때가 아니라, 큐에 넣을 때 해야 합니다.
kmus1232 2년 전
문제에 있는 테스트케이스 모두 정답을 내는 코드입니다
보통 시간초과가 나는 원인인 방문 체크도 확실히 한 것 같은데 왜 시간 초과가 나올까요??