본문 바로가기

알고리즘/백준 풀이

[백준 4963] 섬의 개수

문제 : 섬의 개수


문제 설명 : 아래와 같이 섬과 바다로 구분된 지도상에서 섬의 개수를 구하는 문제.

섬에서 다른 섬으로는 대각선, 가로, 세로로 걸어갈 수 있으며, 갈 수 있으면 같은 섬으로 취급.


-> 전형적인 DFS 문제이다. 




DFS 탐색을 위한 데이터구조

  • 지도 정보
  • 방문 정보
DFS 탐색 조건
  1. 기저 사례
    1. 지도 정보 밖으로 나갈 경우
    2. 이미 방문한 섬인 경우
  2. 나머지인 경우 탐색 계속





Review


DFS 탐색을 진행 시, 기저 사례를 명확히 할 것!

'알고리즘 > 백준 풀이' 카테고리의 다른 글

[백준 1328] 고층 빌딩  (1) 2018.11.29
[백준 9465] 스티커  (0) 2018.11.25
[백준 2163] 초콜릿 자르기  (0) 2018.11.25
[백준 2667] 단지번호 붙이기  (0) 2018.11.25
[백준 1011] 다리 놓기  (0) 2018.10.01