s_lam   11달 전

BFS를 이용해서 답을 도출하는데에는 성공을 했는데, 그렇게 했을 시 이 문제의 시간복잡도가 궁금합니다.

혼자서 공부를 해봤을 때는, 탐색 방향이 4가지 방향이고, N,M의 최댓값이 100이기 떄문에 4^(100 X 100) 만큼 걸린다고 생각했는데

아닌 것 같아서요..

이 문제 처럼 2차원 맵에서 상하좌우 4방향으로 움직일 수 있고, 특정 목표정점까지의 최단거리를 구할 때,

BFS탐색 방법을 사용하게 될 경우 시간복잡도가 궁금합니다 !!

djm03178   11달 전

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

s_lam   11달 전

// djm03178

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

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

djm03178   11달 전

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

djm03178   11달 전

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

s_lam   11달 전

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

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