ETC/Algorithm3 Dijkstra 알고리즘 문제 유형 Dijkstra 알고리즘은 최단 경로를 찾기 위한 알고리즘으로써, 특정 노드에서 다른 노드로의 최단 경로를 찾는 문제에서 사용된다.(모든 노드에서 다른 노드로의 최단 경로를 찾기 위해서는 Floyd Warshall 알고리즘을 사용해야한다) 이번 포스팅에서는 Dijkstra 알고리즘을 활용하는 문제의 유형에 대해 알아보도록 하겠다.(참고: Dijkstra 알고리즘 자체에 대해서는 다루지 않는다)모든 노드로의 최소 경로 찾기Network Delay TimeDijkstra 알고리즘 문제 중 가장 기본적인 유형으로, 이 문제를 풀기 위해서는 시작 노드에서 모든 노드로의 최단 경로를 알아야 한다. 추가적으로 이 문제에서는 모든 노드가 연결되지 않은 경우에 대해서도 다루고 있다.이는 각 노드로의 최소 거리를 확인하.. 2024. 5. 30. BFS (Breadth First Search) 설명 BFS의 경우 DFS와 달리 재귀적으로 처리되지 않고 queue를 사용하여 탐색할 노드의 순서를 저장한다. 이번 포스팅에서는 BFS를 통해 어떻게 node를 탐색하는지에 대해 알아보도록 한다. Binary Tree 기반 BFS 기본적인 Binary Tree 형태로 넓이 우선으로 탐색하는 과정을 살펴보자. Tree는 좌측에 있는 그림과 같은 형태라고 하면, 우측의 화살표 순으로 탐색을 해야한다. 1. 먼저 탐색해야할 node queue에 root node를 추가한다. 2. 탐색해야할 node queue를 보고 node 탐색 iteration이 시작된다. 2.1) (왼쪽) queue를 pop하니 node1을 탐색해야하기 때문에 node1을 탐색한다. (오른쪽) 탐색한 뒤 node1과 연결된 node들(no.. 2024. 2. 13. Graph Number of Islands 이 문제는 크게 2가지 흐름으로 처리한다. 첫 번째는 grid의 모든 cell을 scan 하면서 땅(1)을 찾는 것이다. 그리고 땅이 나오면 인접한 땅이 있는지를 확인하고 해당 땅이 속한 섬을 확인한다. 아래 좀 더 자세하게 설명한다. 먼저 땅을 발견하면 확인한 땅이라고 체크를 하기 위해 해당 cell의 값을 2로 변경한다. 그리고 해당 cell과 인접한 cell에 땅이 있는지를 확인한다. 이를 상좌하우 순으로 확인한다고하면 위쪽 cell은 grid 범위를 벗어나고, 왼쪽 cell은 땅이 아니다. 아래 cell은 땅이므로 해당 cell을 확인된 땅이라고 체크한다. 그리고 새로 확인된 땅이라고 체크해놓은 cell 인접 해당 cell의 윗 cell은 확인된 땅이므로 다시 작업.. 2021. 6. 4. 이전 1 다음
