3-K 플러드필 질문입니다.

Question

안녕하세요! 항상 강의 잘 듣고 있습니다. 3-J와 3-K에서 플러드필을 배우면서 플러드필을 '직전까지 하던 내용을 임시 큐에 저장하고 다음 dfs/bfs시 임시큐의 내용부터 이어서 작업하게 함으로서 새롭게 dfs/bfs를 수행하여 전체를 훑는 것보다 탐색하는 경우의 수를 줄이는 방법'이라고 이해하였습니다. 더 자세히 알고싶어 플러드필을 검색해보니 일반적인 예시는 큰돌님처럼 임시큐에 저장하는 것이 아니라 저희가 int 반환형 dfs와 유사하게 쓰고 있더라구요? 지난 강의에서였나 확실치는 않지만 플러드필이 아니라고 하는 사람도 있지만 이것은 플러드필이 맞다? 라고 하셨던 것 같은 기억이 있습니다. 일단 잘 써먹는게 중요하다라는 생각이지만 정리하자면 일반적으로 사람들이 말하는 int 반환형 dfs 같은 것이 기본적인 플러드필이고, 임시큐를 활용하는 것은 그냥 플러드필에 임시큐를 활용했다 정도로만 알면 될까요? 감사합니다.

큰돌 · Answer

안녕하세요 ㅎㅎ 먼저 DFS 자체는 플루드필이 아닙니다. 첫번째. 컴포넌트들을 번호를 붙여가며 색칠하는 알고리즘 두번째, queue를 2개를 사용하거나 qSize를 통해 단계적으로 BFS하는 것을 얘기하는데 간혹 DFS를 기반으로 재귀적으로 탐색하며 단계적으로 탐색하게 하는 것도 플루드필이라고도 합니다. + int반환형 dfs = 플루드필 은 아닙니다.   감사합니다.