아기상어1 16236 아기상어 시뮬레이션 문제를 해결해보자. 맵이 주어지고, 탐색을 할 경우에 dfs를 쓸 것인지, bfs를 쓸 것인지 고민이 된다. bfs가 dfs를 아우르는 개념이라서 보통 bfs를 쓰면 되는데, 특히 최단경로 문제(가중치가 없을 때)일 때는 bfs를 써야한다. 이 때, visited[][] 대신, dist[][]를 이용하면서 최단경로도 저장하고, 방문했는지도 체크할 수 있다. 처음에 문제를 이해하느라, 시간을 많이 썼지만 차근차근 이해하고, 배운 개념을 써먹으면 문제가 풀린다. 시간복잡도는 모든 물고기 O(V)에 대해 한번 잡아먹을 때마다 다음 잡아먹을 물고기 모두를 탐색해야 하므로 O(|V| + |E|)가 걸린다. O((20 x 20) x (20 x 20 + 19 x 20 x 2) ) = 464,000이 걸린다.. 2019. 9. 29. 728x90 이전 1 다음
