방문 체크를 한다면 같은 정점을 두 번 이상 방문하지 않기 때문에, 모든 정점을 방문하는 시간 + 모든 간선을 확인하는 시간만큼만 걸립니다.

// djm03178

답변 정말 감사한데 제가 아직 무슨 말인지 정확하게 잘 모르겠어 가지구요...

혹시 이 문제의 경우 시간복잡도가 어떻게 나오는지 수치값으로 말씀해 주실 수 있으신가요 ??ㅠㅠ

시간 복잡도는 O(NM)입니다.

풀어서 설명하자면 정점의 개수가 O(NM)개이고, 각 정점에서 연결된 간선이 4개씩이니까 간선의 총 개수는 O(4NM)인데, 상수배는 무시할 수 있으므로 똑같이 O(NM)으로 쓸 수 있습니다. BFS 탐색 과정에서 정점을 O(NM)개 보고 간선도 O(NM)개 보니 O(NM+NM) = O(2NM)인데, 역시 상수배는 무시할 수 있으니 O(NM)입니다.

아하 ! 답변 정말 감사드립니다 !!