개념 및 활용문제들

그래프 탐색 알고리즘 : DFS / BFS

DFS

Depth-First Search

깊이 우선 탐색

BFS

Breadth-First Search

너비 우선 탐색

미리 알고가는 기본적인 자료구조 내용 정리!

스택, 큐, 재귀함수

스택, 큐, 재귀함수란?

<문제> 음료수 얼려 먹기 (연결 요소 찾기 Connected Component)

• NM 크기의 얼음 틀이 있습니다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시됩니다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어있는 경우 서로 연결되어 있는 것으로 간주합니다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하세요. 다음의 45 얼음 틀 예시에서는 아이스크림이 총 3개 생성됩니다.

[문제 해결 아이디어]

• 이 문제는 DFS 혹은 BFS로 해결할 수 있다. 얼음을 얼릴 수 있는 공간이 상하좌우로 연결(인접한 노드 형태)되어 있다고 표현할 수 있으므로 그래프 형태로 모델링 할 수 있다.
• DFS 활용 알고리즘

1. 특정 지점의 상하좌우를 살펴본 뒤에 주변 지점 중에서 값이 0이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문한다.