Flood Fill 알고리즘 리펙토링

컬러 퍼즐 최저 횟수 계산 알고리즘을 만들던 중, 이전에 만들었던 Flood Fill 알고리즘에 문제점이 발견되어 수정하기로 하였다.

문제점

이전 코드

• 이전에 이용하던 Flood Fill 알고리즘이다.
• 일반적인 Flood Fill 방식과 작동 방식이 반대인 것으로 확인되었다.

1. 일반적인 Flood Fill: 시작점에서 인접한 '같은 색상'의 셀들을 탐색하며 새로운 색상으로 칠한다.

2. 현재 코드 (TrySolve): 시작 셀을 선택된 색으로 바꾼 후, 인접한 셀 중 이전 색상(prevColor)과 같은 셀을 찾아 재귀 호출한다.

3. TrySolve는 재귀적 DFS이므로 격자가 깊어지면 스택 오버플로우 위험이 있다.

해결방안

• 반복적인 BFS(Queue 기반)로 FloodFill 함수를 구현.

개선한 코드

• Queue를 이용하여 DFS가 아닌 BFS방식으로 구현하였다. 이로 스택 오버플로를 방지하였다.

Test

• 시각적으로 확인해보기 위해서 20x20 판을 만들어 주고 메모리의 깊이를 측정해 보았다.

Test

TrySolve(DFS 알고리즘)의 경우

FloodFill(BFS 알고리즘)의 경우

• DFS: 스택 깊이 399 -> 스택 메모리 사용
• BFS: 최대 큐 크기 39 -> 힙 메모리 사용
• BFS는 전체 탐색 과정에서 동시에 많은 수의 함수 호출을 발생시키지 않고 안정적인 메모리 사용량을 유지한다는 것을 확인할 수 있다.

소감

원래는 컬러 퍼즐 최저 횟수 계산 알고리즘을 만들려고 Gemini의 도움을 받고 있었는데, BFS와 A스타 알고리즘 중에서 A스타가 더 효율적이라고 해서 해당 알고리즘을 공부하다가 문제점을 찾게 되었다. 생각보다 혼자공부하기에 AI가 많이 도움 되는 것 같다.

부록

참고로 Gemini도 해당 퍼즐을 못 풀었다.

Gemini

• 아마 A스타 알고리즘으로 최저 횟수를 구하더라도 완벽한 해답이 될 것 같지는 않다.