백준 15649번 : N과 M(1)

• 분류: 백트래킹

코드

#include <iostream>

int n, m;
bool visit[9];
int seq[9];

void dfs(int depth) {
    if(depth==m) {
        for(int a=0 ; a<m ; a++) {
            std::cout << seq[a] << ' ';
        }
        std::cout << "\n";
        return;
    }
    for(int i=0 ; i<n ; i++) {
        if(!visit[i]) {
            visit[i] = true;
            seq[depth] = i+1;
            dfs(depth+1);
            visit[i] = false;
        }
    }
}

int main() {
    std::cin >> n >> m;
    dfs(0);
}

• 코멘트
  
  간단한 dfs로 문제를 해결할 수 있다. 문제의 조건에서

  첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

라고 하였으니 적당히 크기 9짜리 배열 두 개를 준비한다. 하나는 수열을 이루는 M개의 원소를 저장할 곳, 하나는 1부터 N까지 N개의 자연수 노드의 방문 여부를 저장하는 곳이다. main 함수에서는 depth=0 으로 탐색을 시작한다. 그리고 재귀적으로 탐색해나간다.

depth=k 레벨에서의 dfs() 함수는 수열의 k번째 원소를 찾는 단계가 된다.

1. 1부터 N까지 for문을 돌며 visit하지 않은 원소를 찾고,
2. 찾았으면 그 원소를 visit으로 체크해주고 seq의 k번째 원소로 추가한다.
3. 그 다음 depth+1 로 다음 dfs 탐색을 떠나면 된다. dfs 탐색의 가장 밑바닥은 depth==m 일 때이니, 이 때는 seq에 저장된 수를 싹 출력하면 된다.