acmicpc.net/problem/15649

DFS(Depth First Search)

가능한 모든 경로를 탐색하는 알고리즘이다.

Backtracking

DFS 등으로 모든 경우의 수를 찾는 과정에서, 이 경우가 답이 되지 않을 것 같으면 그 경로를 그만 탐색하고 되돌아간다.

if문 같은 걸로 구현하는 경우가 많다.

Backtracking의 재귀 구조? 자체를 잘 모르는 상태였기 때문에 그냥 다른 사람의 코드를 참고해서 이해한 후 내가 다시 짜보는 방식으로 했다.

Solution

#include <stdio.h>

void dfs(int* seq, int depth, int n, int m)
{ 
    int i, j;
    int exist=0;
    if(depth==m)
    {
        for(i=0; i<m; i++)
            printf("%d ", seq[i]);
        printf("\n");
    }
    else
    {
        for(i=1; i<=n; i++)
        {
            for(j=0; j<depth; j++)
            {
                exist=0;
                if(seq[j]==i)
                {
                    exist=1;
                    break;
                }
            }
            if(exist==0)
            {
                seq[depth]=i;
                dfs(seq, depth+1, n, m);
            }
        }
    }
}

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    int seq[8]={}; //채울 수열
    dfs(seq, 0, n, m);
}

코드 설명

함수 = void dfs(int* seq, int depth, int n, int m)
1~n까지의 수를 m개 선택해서 만드는 수열이다.
seq = 수열을 보관하는 array
depth = 수열의 길이(DFS에서 탐색한 깊이)
이 깊이가 수열의 최대 길이 m이 될 때 탐색이 종료되고 결과를 출력한다.

i = 수열에 들어가는 숫자
j = 수열 내부에서 같은 수열이 있는지 탐색할 때 사용하는 변수

Recursion(재귀)를 이용한다.

Tip

💡 backtracking에서 아까 방문했던 답인지 아닌지를 판단할 때, exist와 같은 변수를 0으로 초기화시킨 후 존재하면 1을 대입하는 방식으로 확인할 수 있다.

여담

앞으로 변수 이름을 직관적으로 짓는 습관을 들이자... 사실 그 동안 i, j, m, n 이게 습관되어 있었는데 확실히 가독성의 차이가 있는 것 같다.

다음에는 이와 비슷한 문제인 https://www.acmicpc.net/problem/15650 를 풀어보는 걸로 하자.
내일은 진짜 시험 공부 하긴 해야 해서 조오금 그렇다...ㅋㅋ