단단해지기

[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년마다 얼만큼 녹을 지 상하좌우의 빙산을 탐색하여 모든 빙산의 녹는 정도를 구한 후에 빙산을 녹여야한다. 빙..

[백준/BOJ 알고리즘] 3190 뱀 C++

> https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 문제 설명이 잘 돼 있어 재밌게 풀었던 문제이다. 좌표를 나타내기 위해 pair를 사용하였다. 뱀이 차지하고 있는 공간(?)의 좌표를 큐에 담도록 한다. 기본적으로 뱀이 이동할 때 머리가 한칸 전진하고, 꼬리가 따라온다. 사과를 먹었다면 머리만 전진한다고 생각하면 이해가 쉽다. 머리가 한칸 전진 : 새로운 좌표를 큐의 front에 PUSH 꼬리가 따라옴 : 큐의 end 값을 POP 사과를 먹을 때 뱀..