BFS3 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. [최단경로] 다익스트라(Dijstra) 알고리즘 30. 최단 경로 알고리즘 BFS와 구현방법이 상당히 비슷하다. 다익스트라 알고리즘 다익스트라(Dijstra, 데이크스트라) 알고리즘은 다음과 같다. d[v]는 시작점 s로 부터 그래프의 모든 점까지의 최단거리이다. 아이디어는 BFS와 비슷한데, 가중치가 붙어있는 그래프를 다루므로, queue에 넣을 때는 (지금까지 누적 cost, 다음점)을 넣어준다. 매번 while문의 처음에서 cost가 최소인 점을 선택하는 이유는, 최단 거리가 되는 가능성이 있는 점들을 먼저 탐색하고 d[v]를 기록해주기 위함이다. 이렇게 해서 S 안에 다른 원소가 뽑혀 이미 기록된 d[v] 과 비교하여 더 크다면, 무시해주면 된다! 그래프를 직접 그려보면서, 알고리즘을 이해하는 것이 효율적인 것 같다. 이렇게 해서 직접 코드를 .. 2019. 9. 27. [BFS] 너비 우선 탐색 BFS (너비 우선 탐색) 시작점에서 가까운 정점부터 순서대로 방문하는 탐색 알고리즘 각 정점을 방문할 때마다 모든 인접 정점을 검사합니다. 처음 보는 정점을 발견하면 이 점을 방문 예정(discoverd)이라고 기록한 뒤, 별도의 위치(queue)에 저장합니다. 인접한 정점을 모두 검사하고 나면, 저장한 목록에서 다음 정점을 꺼내서 방문합니다. BFS (너비 우선 탐색)에서 새 정점을 발견하는데 사용했던 간선을 모은 트리를 BFS Spanning Tree(너비 우선 탐색 신장 트리) 라고 부릅니다. #include #include using namespace std; // Adjacent List vector adj; vector order; /* start 노드로부터 시작하여 너비 우선 탐색하여 각 .. 2019. 9. 9. 728x90 이전 1 다음
