완전탐색 & 백트래킹 & Flood Fill 수업노트
완전탐색이란?
모든 경우의 수를 탐색하는 방법이다.
1) 브루트포스 (brute force)
단순히 조건문/반복문들을 사용해 모든 경우의수를 계산하여 답을 구하는 방법, N이 커지는 사용할수 없다.
2) DFS/BFS
완전 탐색의 경우의 DFS/BFS가 많이 사용된다. 가령 길찾기/ 최단거리 탐색/ 가능한 조합 중 최적의조합을 모든 경우를 탐색하여 찾아내는 경우가 있다.
완전탐색의 사용 조건
완전탐색의 경우는 데이터의 개수(N)이 작거나, 또는 입의 답 하나를 선택하거나, 여러조건이 가능한경우에 주로 사용된다.
백트래킹이란?
답을 찾는 도중에 막히면 될 수 없다고 판단하면, 되돌아가서 다시 찾아가는 기법
DFS 탐색과의 차이점
DFS 탐색을 하면 모든경로를 다 탐색한다.
모든 경로를 탐색하기 때문에 틀린호한 것같은 경로를 사전에 차단하지 않는다. 그래서 경우수가 줄어들지 않는다.
백트래킹은 완전탐색하는 도중에 탐색에 들어가지 않고 제한조건을 걸어서 특정 조건을 위배가 되는지 안되는지 판단한호예 의해가 되는 경우는 제한하고 탐색한다.
구현 전략
다만 백트래킹 문제를 풀때는 백트래킹인지 DFS 인지 분석해보셔 풀면 시간에 축약한다. 일단 DFS 인지 구현을 할 후에 제외시켜야 할 조건이 있다면 추가시켜서 백트래킹 문제가 자연스럽게 구현이 되는 것이다.
BFS vs DFS 선택
백트래킹은 당연하게도 DFS/BFS 둘다 구현이 가능하다.
다만 이전 수행으로 들어가야 하기 때문에 BFS보다는 DFS가 구현이 더편한경우가 많아서 주로 DFS를 이용해서 문제를 해결한다.
BFS vs DFS 탐색 방식 비교
BFS: 레벨별로 넓게 탐색 (0→1,2→3,4,5,6...)
DFS: 깊이 우선으로 탐색 (0→1→3→4→5→2→4→5→6...)
백트래킹 예시
3x3 행렬 선택 게임
3x3 행렬 선택 게임으로 예시를 든다.
규칙: 아래와 같은 행렬이 존재 할때 3개의 수자를 선택하는데, 단 선택한 숫자들과 행과 열은 모두 중복이 되면 안된다.(즉 뽑아내는 숫자의 행과 열이 모두 달라야한다.)
각 레벨에서 선택 가능한 열을 나타내며, 이미 선택된 열은 제외됩니다.
백트래킹 구현 코드
3x3 매트릭스 백트래킹 구현
#include <iostream>
int matrix[3][3] =
{
{2,4,3},
{1,3,7},
{6,5,6}
};
bool check[3] = {};
void dfs(int row, int score)
{
if (row == 3)
{
std::cout << score << std::endl;
return;
}
for (int i = 0; i < 3; i++)
{
if (check[i] == false)
{
check[i] = true;
dfs(row + 1, score + matrix[row][i]);
check[i] = false;
}
}
}
int main()
{
dfs(0, 0);
return 0;
}
C++
복사
코드 분석
핵심 변수
•
matrix[3][3]: 3x3 게임 매트릭스
•
check[3]: 각 열의 사용 여부 체크 배열
•
row: 현재 행 (레벨)
•
score: 현재까지의 점수 합계
알고리즘 동작
1.
종료 조건: row == 3이면 모든 행을 다 선택했으므로 점수 출력
2.
선택 과정: 각 열(i)에 대해
•
check[i] == false: 아직 사용하지 않은 열인지 확인
•
check[i] = true: 해당 열 사용 표시 (백트래킹 준비)
•
dfs(row + 1, score + matrix[row][i]): 다음 행으로 재귀 호출
•
check[i] = false: 탐색 완료 후 사용 표시 해제 (백트래킹)
백트래킹의 핵심
check[i] = false: 재귀 호출이 끝난 후 상태를 원래대로 되돌리는 것이 백트래킹의 핵심입니다.
Flood Fill (플루드필)
기본 개념
주어진 시작점으로 부터 연결된 영역들을 찾는 알고리즘
다차원 배열의 어떤 간과 연결된 영역을 찾는 알고리즘
예를 들어 그림판의 채우기 기능, 지뢰찾기에서 특정 셀을 클릭시 주변에 지뢰가 없는 모든 셀을 찾아주는 기능
Flood Fill 시각화
시작 상태: → 결과 상태:
┌─────────────┐ ┌─────────────┐
│ □ ■ ■ □ □ │ │ ■ ■ ■ □ □ │
│ □ □ ■ □ □ │ │ ■ ■ ■ □ □ │
│ ■ □ □ □ ■ │ │ ■ ■ ■ □ ■ │
│ ■ ■ □ □ ■ │ │ ■ ■ ■ □ ■ │
└─────────────┘ └─────────────┘
□: 빈 공간 (0) ■: 채워진 공간 (1)
■: 벽 (1) 오렌지: 새로 채워진 영역
Plain Text
복사
Flood Fill 특징
•
연결성: 상하좌우로 인접한 같은 값의 셀들을 모두 찾음
•
재귀적 구조: DFS를 사용해서 구현하는 것이 일반적
•
실무 활용:
◦
그래픽 프로그램: 페인트의 채우기 도구
◦
게임: 지뢰찾기, 테트리스 라인 제거
◦
이미지 처리: 영역 분할, 노이즈 제거
Flood Fill 기본 알고리즘
#include <iostream>
//flood fill
char map[9][10] =
{
"#########",
"#...#...#",
"#...#...#",
"#..#....#",
"###...###",
"#....#..#",
"#...#...#",
"#...#...#",
"#########"
};
void printMap()
{
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
std::cout << map[i][j];
}
std::cout << std::endl;
}
}
void FloodFill(int x, int y)
{
if (map[y][x] == '.')
{
map[y][x] = '@';
FloodFill(x, y + 1);
FloodFill(x - 1, y);
FloodFill(x, y - 1);
FloodFill(x + 1, y);
}
}
int main()
{
printMap();
std::cout << "==========================" << std::endl;
FloodFill(4, 4);
printMap();
return 0;
}
C++
복사
알고리즘 비교 정리
완전탐색 vs 백트래킹
구분 | 완전탐색 | 백트래킹 |
탐색 범위 | 모든 경우의 수 | 조건에 맞는 경우만 |
효율성 | 느림 (모든 경우) | 빠름 (가지치기) |
구현 | 단순 | 조건 검사 필요 |
메모리 | 많이 사용 | 적게 사용 |
DFS vs BFS (백트래킹 관점)
구분 | DFS | BFS |
백트래킹 | 쉬움 (자연스러운 되돌아가기) | 어려움 |
메모리 | 적음 (재귀 스택) | 많음 (큐 사용) |
구현 | 간단 | 복잡 |
활용 | 조합, 순열, 경로 탐색 | 최단 경로 |
실무 활용 사례
백트래킹 활용
•
N-Queen 문제: 체스판에서 퀸 배치
•
스도쿠 솔버: 숫자 배치 퍼즐
•
미로 찾기: 모든 가능한 경로 탐색
•
조합 최적화: 배낭 문제, 여행자 문제
Flood Fill 활용
•
이미지 편집: 포토샵 마술봉, 페인트 채우기
•
게임 개발: 연결된 블록 찾기, 영역 계산
•
지도 분석: 연결된 지역 찾기
•
네트워크 분석: 연결된 노드 그룹 찾기
핵심 포인트
백트래킹의 핵심
1.
조건 검사: 유망하지 않은 경우 미리 차단
2.
상태 복원: 탐색 후 원래 상태로 되돌리기
3.
가지치기: 불필요한 탐색 경로 제거
4.
DFS 활용: 깊이 우선 탐색이 구현하기 용이
Flood Fill의 핵심
1.
연결성 검사: 같은 값의 인접한 셀들만 탐색
2.
재귀 구조: DFS로 연결된 모든 영역 방문
3.
경계 처리: 배열 범위 벗어나지 않도록 주의
4.
무한 루프 방지: 이미 방문한 곳은 다른 값으로 변경
백트래킹과 Flood Fill은 모두 DFS를 기반으로 하는 강력한 알고리즘 기법들입니다.
“강의는 많은데, 왜 나는 아직도 코드를 못 짤까?”
혼자 공부하다 보면 누구나 이런 고민을 하게 됩니다.
•
강의는 다 들었지만 막상 손이 안 움직이고,
•
복습을 하려 해도 무엇을 다시 봐야 할지 모르겠고,
•
질문할 곳도 없고,
•
유튜브는 결국 정답을 따라 치는 것밖에 안 되는 것 같고.
문제는 ‘연습’이 빠졌기 때문입니다.
단순히 강의를 듣는 것만으로는 실력이 늘지 않습니다.
실제 문제를 풀고, 고민하고, 직접 구현해보는 시간이 반드시 필요합니다.
그래서, 얌얌코딩 코칭은 다릅니다.
그냥 가르치지 않습니다.
스스로 설계하고, 코딩할 수 있게 만듭니다.
얌얌코딩 코칭에서는 단순한 예제가 아닌,
스스로 문제를 분석하고 구현해야 하는 연습문제를 제공합니다.
이 연습문제들은 다음과 같은 역량을 키우기 위해 설계되어 있습니다:
•
문제를 스스로 쪼개고 설계하는 힘
•
다양한 조건을 만족시키는 실제 구현 능력
•
기능 단위가 아닌, 프로그램 단위로 사고하는 습관
•
마침내 자신의 힘으로 코드를 끝까지 작성하는 경험
지금 필요한 건 더 많은 강의가 아닙니다.
코드를 스스로 완성해 나가는 훈련,
그것이 지금 실력을 끌어올릴 가장 현실적인 방법입니다.
자세한 안내 보기: 프리미엄 코칭 안내 바로가기 또는 카카오톡 상담방: 얌얌코딩 상담방