[알고리즘][DFS] 영역 구하기 (정올)

DFS(백트래킹) 알고리즘 문제 : 영역구하기 (정올)

오랜만에 DFS(백트래킹) 알고리즘을 풀어보았다.

DFS는 흔히 재귀로 많이 풀기 때문에 소위 말하는

재귀적인 사고(?)가 필요하다. 코드를 설명하는 부분에도

이러한 부분을 설명하기가 상당히 까다롭기 때문에

설명이 조금 부실하다.

일단 DFS(백트래킹)은 깊이 우선 탐색을 한다.

쉽게 말해 한 방향으로 쭉 들어갔다가 빠져나오는 것

스택의 원리와 같기 때문에 스택을 이용하거나

함수가 스택에 쌓였다가 풀리는 과정을 이용(재귀)

하여 풀 수 있다. 이번 문제는 난이도가 높지는 않은 듯 하다.

01. 변수 선언, 초기화

DFS (백트래킹)문제를 잘 풀기 위해서는

문제를 제대로 이해하고 초기화 하는 것 부터 시작.

02. 재귀 함수

최대한 자세히 설명한다고 했지만

재귀적인 사고(?)가 필요함.

03. 메인 함수

위에 코드에서도 언급했지만

한번의 함수호출로 답을 찾아낼 수 있는 방법이

있는지 조금 더 생각해봐야 할 부분이다.

오늘은 오랜만에 DFS(백트래킹) 알고리즘을 풀어보았다.

사실 초반에 BFS로 풀까 말까 고민하다가 정신없었던 건 사실

DFS, BFS에 익숙해져서 어떠한 알고리즘을 써야하는지

한번에 캐치하는 것도 중요한 듯 하다.