문제)
입력)
첫 번쨰 줄에 얼음 틀의 세로 길이 n 과 가로 길이 m이 주어집니다.
두 번째 줄부터 n + 1 번째 줄까지 얼음 틀의 형태가 주어집니다.
이때 구멍 뚫려있는 부분은 0, 그렇지 않은 부분은 1입니다.
출력)
한번에 만들 수 있는 아이스크림 개수를 출력 합니다.
입력 예시)
4 5
00110
00011
11111
00000
출력 예시)
3
시간 제한: 1초 / 메모리 제한: 128MB
문제 풀이)
- dfs를 활용하는 알고리즘은 다음과 같다.
- 특정한 지점의 주변 상, 하, 좌, 우를 살펴본 뒤에 주변 지점 중에서 값이 '0' 이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문
- 방문한 지점에서 다시 상, 하, 좌, 우를 살펴보면서 방문을 진행하는 과정을 반복하면, 연결된 모든 지점을 방문 할 수 있다.
- 모든 노드에 대하여 1~2번 과정을 반복하며, 방문하지 않은 지점의 수를 카운트
:)