탐색 3

[백준][DFS] 99클럽 코테 스터디 4일차 TIL + 안전 영역 (+ RecursionError 핸들링 하기)

오늘의 학습 키워드DFS, 시뮬레이션 오늘의 회고🌱 오늘의 문제 https://www.acmicpc.net/problem/2468(왜 미리보기가 안 불러와질까 🥹)2차원 배열이 주어지고 각각의 칸에는 지형의 높이 정보를 나타내는 자연수 값이 들어간다.이 문제에서는 장마철에 특정 높이 이상 비가 와 일부 지형이 물에 잠겼을 때, 물에 잠기지 않은 안전 영역의 최대 개수를 묻고 있다.여기서 안전 영역은 상하좌우로 인접해 있는 지점들이 최대를 이루는 영역을 말한다.  🌱 나의 시도최대 영역에 대한 개수를 세는 문제는 마침 어제 공부한 DFS 문제의 예시와 비슷했다.그래서 나는 이 문제를 재귀 함수를 이용한 DFS로 구현해보려고 한다.또한 이 문제에서는 장마철에 오는 강우량의 '높이'에 대해 명시하지 않으..

Daily/Coding Test 2025.04.04

[알고리즘] DFS(Depth-First Search)와 BFS(Breadth-First Search)

0. IntroductionDFS와 BFS를 별도 게시물로 정리하려고 했으나 결국 하나의 게시물로 정리하게 되었다.둘은 이름이 비슷해서인지 잘 헷갈리는 것 같다.같은 게시물 안에서 동일한 그래프로 비교하면서 보면 더 잘 이해할 수 있을 것이라고 판단하였다.단, BFS, DFS 문제풀이는 본 게시물에서 다루지 않는다. 앞으로 DFS, BFS 문제를 공부하면서 차근차근 하나씩 추가해보겠다. 1. DFS (Depth-First Search, 깊이 우선 탐색)1. 정의이름에서 알려주는 것처럼 깊이를 우선적으로, 즉, 가장 깊이 위치하는 노드까지 탐색하는 알고리즘이다.DFS 문제를 풀 때는 스택을 활용하면 더 쉽게 해결할 수 있다.이것은 예시를 보면 더욱 잘 이해할 수 있으니 예시를 함께 보면서 확인하도록 하자...

[자료구조] 그래프(Graph)와 탐색(Search)

🌱 그래프 그래프는 노드와 간선으로 이루어진 자료 구조이다. 크게 노드와 엣지(간선)으로 구성되어 있다.그래프는 간선으로 연결된 노드들 간 이동할 수 있는데, 이렇게 간선으로 연결된 노드들을 인접하다(Adjacent)고 한다.  🌱 그래프 표현 방법그래프에서 인접한 노드들간의 관계를 나타내는 방법으로 크게 인접 행렬(Adjacency matrix)과 인접 리스트(adjacency list)가 있다.1. 인접 행렬인접 행렬은 단어 그대로 "행렬"의 형태로 인접한 노드 간의 관계를 나타낸 것을 의미한다.행의 노드와 열의 노드 간의 거리를 행렬값으로 확인할 수 있다. 따라서 인접한 노드 조회를 할 때 시간 측면에서 O(1)로 아주 빠르다.그러나 이 방식은 메모리 측면에서 비효율성을 야기할 수 있기에 조심해..