Algorithm - Recursion, DFS, Backtracking (Baekjoon 15649, 15650, 15651, 15652 C)

jir4vvit

2023-02-02

Docs › Algorithm

Backtracking, Baekjoon, C, DFS, Recursion

TL;DR

https://solved.ac/en/profile/cutieee

요즘 C로 백준을 꾸준히 풀고 있다. 이 글을 시점으로 Streak 54 days를 달성했다. 짝짝짝! 어제쯤 실버 2를 달성했는데 요즘 들어 알고리즘을 따로 공부해야할 필요성을 느낀다. 그냥 풀게 되면 시간 초과가 나기 일수. 혹은 문제 풀이 방향성을 잡기가 힘들다.

백준 15649, 15650, 15651, 15652 문제를 풀면서 재귀, DFS, 백트래킹 개념을 다질 수 있었다. 백준 사이트에서 단계별로 풀어보기에서 백트래킹 입문 문제를 스스로 풀이하였다. 문제를 풀이하면서 얻은 지식을 블로그에 정리해놓으려고 한다.

이 글의 목표는 백트래킹을 이해하고 백준 15649, 15650, 15651, 15652 문제를 푸는 것이다.

Recursion 재귀

재귀 함수를 아래와 같이 표현할 수 있다.

#include <stdio.h>

int func(int n) {
    if (n == 5)
        return 0;

    printf("%d\n", n);
    return func(n+1);
}

int main() {
    func(0);
}

output

func 함수는 n+1을 인자로 자기 자신을 다시 호출한다. n이 5일 때 출력하지 않고 종료한다.

재귀 함수는 주로 가독성을 위해 쓰여진다. (이론적으로 재귀함수는 for문과 while문 등으로 표현할 수 있다.) 재귀 함수에 대한 이해가 어려운 이유는 재귀 함수를 일반 함수와 다르게 생각하기 때문이다. 사실 흔히 아는 일반 함수와 같다고 생각하면 이게 무엇인지는 바로 이해가 될 것이다.

DFS

DFS(Depth - First - Search)는 깊이 우선 탐색을 의미한다. 어떠한 내용을 브루트 포싱할 때 제일 깊이 내려가서 아래단부터 탐색하는 것을 의미한다. 아래 gif를 보면 잘 이해가 될 것이다.

DFS는 주로 그래프나 트리와 연관되어 사용된다고 한다. 코드는 아래 백트래킹 설명에서 한꺼번에 살펴보자.

DFS는 조건 상관없이 모든 것을 탐색해야 한다. 백준 15649 N과 M (1) 보다 백준 15651 N과 M (3) 부터 풀이를 진행하는 것이 백트래킹 이해에 더 도움이 될 듯 하다. (스포지만 (3)은 백트래킹 개념 없이 DFS만을 가지고 풀이할 수 있다.)

https://www.acmicpc.net/problem/15651

Backtracking

위의 DFS에서 봤던 트리를 잠깐 상상해보자. 정답을 찾기위해 부모 노드에서 자식 노드까지 내려간다. 이때 어떠한 조건에 부합하는 경우만 자식 노드로 내려가고 그렇지 않다면 다시 부모 노드로 올라간다. 이러한 조건에 부합한다.를 유망하다. 라고 표현한다. 조건에 부합하지 않은, 즉 유망하지 않은 노드는 확인을 안하기 때문에 풀이 시간을 단축할 수 있다.

트리로 예시를 들었지만 사실 구현은 큐나 재귀함수로 많이 한다고 한다. 이 글에선 재귀함수로 문제를 풀이하도록 한다.

void DFS(int depth) {
    if (정답이라면) {
        정답 출력 후 종료
    } else { //정답이 아니라면
        for (모든 자식 노드에 대해서) {
            if (정답에 유망하다면) {
                자식 노드로 이동
                DFS(depth + 1);
                부모 노드로 이동
            }
        }
    }
}

재귀 함수 밑에 나오는 문장은 어떻게 이해해야 할까?
정답에 유망하다면 자식 노드를 일단 선택한 뒤에, 그걸 선택한 후 해결한 뒤에, 다시 원래의 상태로 되돌린다.(부모 노드로 이동)

백준 15649 N과 M (1)

https://www.acmicpc.net/problem/15649
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열. 한 마디로 nPm을 구하는 문제.
input
1
4 2

output

#include <stdio.h>
#include <stdbool.h>

int n, m;
int data[10];
bool visit[10];

void DFS(int depth) {
    if (depth == m) {
        // print
        for (int i = 0; i < m; i++) {
            printf("%d ", data[i]);
        }
        printf("\n");
        return;
    } else {
        for (int i = 1; i <= n; i++) {
            if (visit[i] == false) {
                data[depth] = i;
                visit[i] = true;
                DFS(depth+1);
                visit[i] = false;
            }
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);
    DFS(0);
}

중복을 위해 사용한 visit 배열은 값이 사용했나 안했나를 판단하는 배열이다. (값을 인덱스로 활용한다.) 입력이 1부터 시작하기 때문에 visit 배열 인덱스를 1부터 사용한다. 지금 생각해보면 check의 네이밍이 좀 더 어울리는 것 같기도 하다. 가독성을 위하여 bool 타입으로 지정하였다. false라면 사용을 하지 않았기 때문에 data 배열에 값을 넣어주고 해당 값을 인덱스로 가지는 visit 배열을 true로 세팅한다. 그리고 그 다음 자식 노드를 탐색한다.

만약 유망하지 않다면 i++로 다음 반복문을 돈다.

depth가 m과 같을 경우엔 트리 끝까지 다 내려갔기 때문에 data 배열이 출력된다. 잊으면 안되는 것이 m이 출력해야할 숫자 수이다. 어쩌면 이 조건은 당연한 것일지도 모른다. 헷갈리지 말자.

이 문제를 이해하면 다음 2, 3, 4는 매우 쉽게 풀이할 수 있다. 내가 그랬다.

백준 15650 N과 M (2)

https://www.acmicpc.net/problem/15650
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열. 추가로 오름차순이어야 함.
input
1
4 2
output
1
2
3
4
5
6
1 2
1 3
1 4
2 3
2 4
3 4
이 전 문제와 다르게 오름차순이 아닌 경우면 출력을 하지 않는다.

#include <stdio.h>
#include <stdbool.h>

int n, m;
int data[10];
bool visit[10];

void DFS(int depth, int pre) {
    if (depth == m+1) {
        // print
        for (int i = 1; i <= m; i++) {
            printf("%d ", data[i]);
        }
        printf("\n");
        return;
    } else {
        for (int i = 1; i <= n; i++) {
            if (visit[i] == false && pre < i) {
                data[depth] = i;
                visit[i] = true;
                DFS(depth+1, i);
                visit[i] = false;
            }
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);
    DFS(1, 0);
}

이 전 코드에서 pre < i 조건을 추가해주었다. 이때 주의해야할 점은 pre가 등장했기 때문에 main 함수에서 depth 1부터 탐색한다. 즉 data 배열을 인덱스 1부터 사용한다. 그래서 출력할 때 for (int i = 1; i <= m; i++) 조건으로 해야한다.

백준 15651 N과 M (3)

https://www.acmicpc.net/problem/15651
1부터 N까지 자연수 중에서 M개를 고른 수열. 중복 허용
input
1
4 2

output

N과 M (1) 문제와 비교해서 중복이 허용되었다. 사실상 이 문제가 구현하기 가장 쉬울 것 같다.

#include <stdio.h>
#include <stdbool.h>

int n, m;
int data[10];

void DFS(int depth) {
    if (depth == m) {
        // print
        for (int i = 0; i < m; i++) {
            printf("%d ", data[i]);
        }
        printf("\n");
        return;
    } else {
        for (int i = 1; i <= n; i++) {
            data[depth] = i;
            DFS(depth+1);
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);
    DFS(0);
}

조건 없이 모든 것을 다 완전히 탐색하기 때문에 백트래킹 알고리즘은 사용되지 않았다. DFS로 완전탐색한다.

백준 15652 N과 M (4)

https://www.acmicpc.net/problem/15652
1부터 N까지 자연수 중에서 M개를 고른 수열. 중복 허용. 비내림차순
input
1
4 2

output

길이가 K인 수열 A가 A1 ≤ A2 ≤ … ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

#include <stdio.h>

int n, m;
int data[10];

void DFS(int depth, int pre) {
    if (depth == m+1) {
        // print
        for (int i = 1; i <= m; i++) {
            printf("%d ", data[i]);
        }
        printf("\n");
        return;
    } else {
        for (int i = 1; i <= n; i++) {
            if (pre <= i) { // 비내림차순
                data[depth] = i;
                DFS(depth+1, i);
            }
        }
    }
}

int main() {
   scanf("%d %d", &n, &m);
   DFS(1,0);
}

N과 M (2)에서 오름차순을 구현했다면 쉽게 유망한 조건에 비내림차순을 구현할 수 있다.

TL;DR

Recursion 재귀

DFS

Backtracking

백준 15649 N과 M (1)

백준 15650 N과 M (2)

백준 15651 N과 M (3)

백준 15652 N과 M (4)

Reference