dfs

문제) N × M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하라. 다음의 4 × 5 얼음 틀 예시에서는 아이스크림이 총 3개가 생성된다 입력 조건) 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다. (1

DFS (Depth-First Search)란 깊이 우선 탐색의 약자로 그래프의 탐색(traversal, 순회) 방법 중 하나이다. 이 탐색 알고리즘은 말그대로 특정한 경로로 노드를 탐색하다가 가장 깊은 곳까지 탐색하고 경로를 다시 돌아가 다른 경로로 탐색하는 방식을 보인다. 구체적인 DFS의 동작 과정은 아래와 같다. DFS의 동작과정 1. 탐색을 시작하는 노드를 스택에 삽입하고 방문 처리한다. 2. 스택의 최상단 노드에 인접한 노드가 있을 때 아래와 같은 경우에 나누어서 처리한다. 2-1. 인접 노드 중 방문하지 않은 노드가 존재할 때, 그 노드를 방문하고 스택에 삽입, 방문 처리한다. 2-2. 인접 노드 중 방문하지 않은 노드가 존재하지 않을 때, 스택의 최상단 노드를 꺼낸다. 3. 과정2를 더 이..