[Algorithm] DFS - ‘음료수 얼려 먹기’

📣 학습한 내용을 정리한 글입니다.

DFS 알고리즘 문제입니다. 문제에 대한 내용과 풀이 그리고 결과를 간단하게 작성하였으니 참고바랍니다.
풀이 언어 : Python

문제 설명

---

내용

N x M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이락 존재하는 부분은 1로 표시된다.
이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 얼음 틀의 세로길이 N과 가로 길이 M이 입력된다. (1 <= N, M <= 1,000)
두 번째 줄부터 N+1번째 줄까지 얼음 틀의 형태가 주어진다.
이때 구멍이 뚫려있는 부분은 0, 그렇지 않은 부분은 1입니다.

출력

첫째 줄에 한 번에 만들 수 있는 아이스크림의 개수를 출력한다.

문제 풀이

---

DFS Algorithm 참고내용

• DFS는 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
  
• 스택 자료구조(혹은 재귀 함수)를 이용한다.
  

위 참고사항을 준수하며, 풀어보자.
특정한 지점의 주변 상, 하, 좌, 우를 살펴본 뒤 주변 지점 중에서 값이 ‘0’이면서 아직 방문하지 않은 지점을 찾는다.
이를 반복하면 연결된 모든 지점을 방문할 수 있으며, ‘1’이 아닌 ‘0’의 값을 찾을 수 있고 연결되어있는 지점을 분할시켜 카운트하면 결과 값을 구할 수 있다.

작성 코드

Python

DFS 알고리즘

BFS 알고리즘

---

참고 : ‘동빈나’님의 (이코테 2021 강의 몰아보기) 3. DFS & BFS 영상

---