목록너비우선탐색 (1)
유진정의 기록
섬의 개수 - DFS vs BFS로 탐색 알고리즘 비교하기
깊이 들어갈 것인가, 넓게 펼칠 것인가?🏝️ 문제 소개: 섬의 개수를 세는 방법"섬의 개수"는 백준 온라인 저지의 대표적인 DFS/BFS 문제다.지도는 바다(0)와 땅(1)으로 이루어진 2차원 그리드이며, 서로 연결된 1의 집합을 하나의 섬으로 본다. 이때 연결은 상하좌우 + 대각선 총 8방향으로 이루어진다. 목표는 지도에서 총 몇 개의 섬이 있는지 세는 것이다.예시 입력5 41 1 1 1 01 1 0 0 01 0 0 1 10 0 0 1 1출력2🔍 탐색 방법의 핵심: DFS vs BFS이 문제의 핵심은 탐색(Traversal) 이다. 땅(1)을 발견했을 때, 연결된 모든 땅을 순회하며 방문 처리하고 하나의 섬으로 세는 방식이다.여기에는 두 가지 접근 방식이 있다.DFS (Depth-First Sear..
개인공부/데이터분석&알고리즘
2025. 4. 15. 11:02