개요
이번 주차는 코딩테스트의 꽃, 백트래킹과 DFS 그리고 BFS에 대해 학습해보려고 합니다!
그만큼 코딩테스트에 단골 문제로 DFS 혹은 BFS가 나옵니다.
기본적인 문제들도 백준 티어가 최소 실버3? 혹은 실버2부터 시작합니다. 본격적으로 난이도가 올라가는 만큼 이 강의 노트에 만족하지 않고, 구글링을 통해 찾아보는 것도 많은 도움이 될 것 같습니다!
백트래킹
백트래킹은 모든 가능한 경우의 수를 탐색하는 알고리즘 기법으로, 유망하지 않은 경로는 더 이상 탐색하지 않고 되돌아갑니다. 이를 통해 불필요한 탐색을 줄이고 효율적으로 문제를 해결할 수 있습니다.
재귀적으로 문제를 해결하되 현재 재귀를 통해 확인 중인 상태가 제한 조건에 위배가 되는지 판단하고, 해당 상태가 위배되는 경우 해당 상태를 제외하고 다음 단계로 넘어가는 방식입니다.
여기서 “확인 중인 상태가 제한 조건에 위배가 되는지 판단하고, 해당 상태가 위배되는 경우 **해당 상태를 제외” 한다는 의미로 이를 가지치기**라고도 합니다.
주로 모든 경우의 수를 탐색하므로 DFS를 사용해 모든 경우의 수를 탐색하는 과정에서, 조건문 등을 통해 답이 될 수 없는 상황을 정의하고, 이런 상황일 경우엔 탐색을 중지하고 그 이전으로 돌아가 다시 다른 경우를 탐색하도록 만듭니다.
그래프 탐색 (DFS & BFS)
그래프 탐색은 그래프에서 특정 노드를 방문하거나, 특정 조건을 만족하는 노드를 찾는 것을 의미합니다.
이를 위해 사용되는 DFS(깊이 우선 탐색) 과 BFS(너비 우선 탐색)에 대해 설명하겠습니다.
DFS와 BFS의 차이
예시를 위해 가져온 DFS와 BFS 작동 방식입니다.
즉 어떤 노드를 기준으로 깊이(자식)을 먼저 탐색하는가? 혹은 너비(형제)를 먼저 탐색하는가에 차이입니다.
DFS (Depth First Search)
(https://gongbu-ing.tistory.com/58 블로그를 참고했습니다.)
DFS의 진행 방식입니다.
시작 정점을 기준으로 한 노드를 선택해 우선적으로 끝까지 탐색한 후 다른 인접한 노드로 방문할 수 있습니다.
→ DFS는 그래프의 모든 노드를 방문하고자 할 경우 유용합니다.
코드 구현 방식은 재귀 혹은 Stack 을 사용합니다. 기본적으로 저는 Stack을 사용해서 푼 기억은 많이 없습니다 ㅎ…
그렇기에 이 또한 위 블로그 예시로 대체합니다.
void dfs(int depth, int before) {
if(depth == n) return;
for (int i = 0; i < n; i++) {
if(linked[before-1][i] && !visit[i]) {
visit[i] = true;
dfs(depth + 1, i + 1);
}
}
}이는 한 곳을 지정한 후 그 노드을 쭉 탐색하는 방식입니다.
BFS (Breadth First Search)
DFS와 달리 시작 노드에서 인접한 노드들을 차례대로 방문하는 것을 볼 수 있습니다.
BFS는 DFS와 달리 Queue를 주로 사용하고 재귀 방식은 사용하지 않습니다.
0. 시작 노드만 저장된 큐를 준비한다.
1. 시작 노드에 방문한다. (방문 여부 체크)
2. 큐에서 노드를 꺼낸다.
3. 꺼낸 노드에 방문한다. (방문 여부 체크)
4. 큐에 인접한 노드들을 추가한다.
※ 단, 방문 여부를 판단하여 방문한 적 있는 노드는 추가를 하지 않는다. 이를 어기면 무한 루프에 빠지게 된다.
5. 큐에 저장된 노드가 없을 때까지 2 ~ 4번을 반복한다.
예시 코드입니다.
void bfs() {
Queue<Integer> qu = new ArrayDeque<Integer>();
qu.add(v); // 시작할 정점 대기열에 추가
while(!qu.isEmpty()) { // 큐가 완전히 비어있을 때까지 루프
int el = qu.poll(); // 큐의 맨앞 요소를 꺼낸다.
for (int i = 0; i < n; i++) {
if(linked[el-1][i] && !visit[i]) { // 노드가 서로 연결되있고 방문한 적 없다면?
visit[i] = true; // 방문여부 추가!
qu.add(i+1); // 방문한 적 없는 노드의 이웃을 전부 큐에 추가
}
}
}
}예시 문제
바이러스 (https://www.acmicpc.net/problem/2606)
DFS와 BFS를 알아볼 수 있는 간단한 문제입니다.
1번 풀이 (DFS)
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool visited[101]; //방문 여부 확인용
vector<int> graph[101]; //그래프 (인접 리스트 방식)
int cnt = 0; //감염된 컴퓨터 수를 세는 변수
void dfs(int x)
{
visited[x] = true;
for (int i = 0; i < graph[x].size(); i++) // 인접한 노드 사이즈만큼 탐색
{
int y = graph[x][i];
if (!visited[y]) {
// 방문하지 않았으면 즉 visited가 False일 때 not을 해주면 True가 되므로
//아래 dfs 실행
dfs(y); // 재귀적으로 방문
cnt++;
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N,computer;
// N은 컴퓨터 수, E는 연결된 쌍의 수
cin >> N >> E;
int x, y;
for (int i = 0; i < E; i++) {
cin >> x >> y;
graph[x].push_back(y);
graph[y].push_back(x);
}
dfs(1); // 1번 컴퓨터에서 시작
cout << cnt << "\n";
return 0;
}2번 풀이(BFS)
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
bool visited[101]; // 방문 여부 확인용
vector<int> graph[101]; // 그래프 (인접 리스트 방식)
int cnt = 0; // 감염된 컴퓨터 수를 세는 변수
queue<int> q;
void bfs(int start) {
visited[start] = true;
q.push(start);
while (!q.empty()) {
int x = q.front();
q.pop();
for (int i = 0; i < graph[x].size(); i++) { // 인접 노드 탐색
int y = graph[x][i];
if (!visited[y]) { // 방문하지 않은 노드만 탐색
visited[y] = true;
q.push(y);
cnt++; // 감염된 컴퓨터 수 증가
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N, E; // N은 컴퓨터 수, E는 연결된 쌍의 수
cin >> N >> E;
for (int i = 0; i < E; i++) {
int x, y;
cin >> x >> y;
graph[x].push_back(y);
graph[y].push_back(x);
}
bfs(1); // 1번 컴퓨터에서 시작
cout << cnt << "\n";
return 0;
}
2번째 예시 문제입니다.
유기농 배추(https://www.acmicpc.net/problem/1012)
주로 이런 류의 문제를 많이 보게 될 것입니다. 즉 어떠한 범위가 있고, 그 범위 안에서의 특정 조건을 만족시키는 값을 찾으라는 방식입니다.
저는 해당 문제를 DFS를 통해 해결했습니다.
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int MAX = 50; // 최대 가로, 세로 크기
int map[MAX][MAX]; // 배추밭 지도
bool visited[MAX][MAX]; // 방문 여부
int dy[] = {0, 0, -1, 1}; // 상하좌우
int dx[] = {-1, 1, 0, 0};
int M, N, K; // 가로, 세로, 배추 개수
int ans;
void dfs(int x, int y) {
visited[x][y] = true;
for (int i = 0; i < 4; i++) {
int temp_x = x + dx[i];
int temp_y = y + dy[i];
if (temp_x >= 0 && temp_y >= 0 && temp_x < M && temp_y < N) {
if (map[temp_x][temp_y] == 1 && !visited[temp_x][temp_y]) {
dfs(temp_x, temp_y);
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int T; // 테스트 케이스 수
cin >> T;
while (T--) {
cin >> M >> N >> K;
// 초기화
memset(map, 0, sizeof(map));
memset(visited, false, sizeof(visited));
ans = 0; //배추흰지렁이 마리 수
for (int i = 0; i < K; i++) {
int x, y;
cin >> x >> y;
map[x][y] = 1; // 배추 위치 설정
}
for (int j = 0; j < M; j++) {
for (int k = 0; k < N; k++) {
if (map[j][k] == 1 && !visited[j][k]) {
dfs(j, k); // 새로운 영역 탐색
ans++;
}
}
}
cout << ans << "\n";
}
return 0;
}
문제 풀이 순서
1. 각각의 테스트 케이스 수를 입력 받는다.
2. map 크기 즉, 배추 밭 크기와 방문 여부를 초기화한다.
3. 각각의 입력을 받는다. (배추 위치 1로 설정)
4. 2중 for문을 통해 해당 위치에 배추가 있고, 방문하지 않은 곳을 탐색한다.
5. 해당 위치에서 DFS 알고리즘을 실행한 후 배추흰지렁이 마리 수를 추가한다.
DFS 알고리즘
1. 해당 위치를 방문 처리한다.
2. 해당 위치에서 동서남북으로 이동했을 경우를 따진다.
3. 해당 위치가 배추 밭 안에 있는 지 확인한다. (배열 기준으로 0보다는 크고 M과 N보다는 작은 지 확인)
4. 만약 동서남북으로 이동한 위치에 배추가 있다면, 재귀 방식으로 해당 위치에서 DFS를 실행한다.
문제 푸는데 도움이 됐으면 좋겠습니다! 감사합니다!
