dfs

[Algorithm] 깊이우선탐색 DFS 에 대하여

# 그래프 순회 (Graph Traversal) 그래프의 모든 정점을 방문하는 것, 방문하는 방법. 그래프 순회 다음과 같은 그래프가 있을 때, 4개의 정점(노드, vertex)을 확인할 수 있을 것이다. 1, 2, 3, 4 총 4개의 정점을 모두 방문하는 것. 이를 그래프 순회라 부른다. 그래프 순회 알고리즘 그래프 순회 알고리즘에는 대표적으로 두가지가 있다. 1. 깊이우선탐색, DFS 2. 너비우선탐색, BFS 이번 포스트에서는 깊이우선탐색, DFS에 대해서 다룰 것이다. DFS란 ? Depth-First-Search. 깊이우선탐색. DFS. 깊이를 우선적으로 고려하여 모든 정점을 순회하는 알고리즘. 더 이상 갈 수 있는 정점이 존재하지 않을 때까지 정점을 타고 내려간 후에, 갈림길까지 돌아가서 다시..

[백준/BOJ 알고리즘] 2573 빙산 C++

> www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 � www.acmicpc.net 오랜만에 알고리즘 풀다가 마음대로 안되서 화가 났던 문제이다..... 그래도 맞아서 기분 좋다. 기본적인 그래프 탐색을 통해 해결할 수 있는 문제이다. 난 DFS를 통해 구현했다. 문제의 핵심 빙산 높이가 담긴 배열의 가장자리는 모두 0 이므로, 탐색대상에서 제외해야한다. 각 빙산의 높이가 1년마다 얼만큼 녹을 지 상하좌우의 빙산을 탐색하여 모든 빙산의 녹는 정도를 구한 후에 빙산을 녹여야한다. 빙..