N과 m (1)

[Silver III] N과 M (1) - 15649

문제 링크

성능 요약

메모리: 1116 KB, 시간: 36 ms

분류

백트래킹

제출 일자

2023년 12월 31일 18:23:00

문제 설명

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력

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

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

TIL

• DFS의 일종인 BackTracking을 이용한 탐색.
• 무식하게 하나 출력하고 다음 재귀를 진행하는 것이 아니라, 일단 arr배열에 담고 이를 마지막에 한번에 딱 출력하는 게 좋다.
• DFS 진행하면서 depth가 깊어지면서 내려가다가, 종료조건을 만나서 BackTracking하면서 올라올때, 다시 원상태로 되돌리면서 올라와라. (이 문제의 경우는 isVisted=false)

BackTracing

1. 확장
2. 가지치기
3. 끝까지 간뒤에 다시 올라오기 (이때 원상태로 복원시키면서)

---

categories:

• 백준

---

Feedback

• 백트래킹 문제를 처음 접해보는 거라 삽질을 많이 했다.
• 백준의 M과 N 시리즈를 많이 풀어보면서 감을 잡아야겠다.

내 접근

하나하나씩 출력하려 했으나, 그냥 모아서 depth가 최대로 깊어 질 때 한번에 출력하는 게 좋다.

내 코드

#include <stdio.h>
#include <stdbool.h>
#define SIZE 9
void permutation(int* arr, bool* isVisted, int N, int M, int depth);
int main(){

    int arr[SIZE] = {0}; // 순열을 저장하는 배열
    bool isVisted[SIZE] = {0}; // 방문 여부를 저장하는 배열

    //input
    int N, M;
    scanf("%d %d", &N, &M);

    permutation(arr, isVisted, N, M, 0);

    return 0;
}

void permutation(int* arr, bool* isVisted, int N, int M, int depth){
    if(depth == M){ // depth가 M이랑 같으면 arr 출력
        for(int i = 0; i < M; i++){
            printf("%d ", arr[i]);
        }
        printf("\n");
        return;
    }
    for(size_t i = 1; i <= N; i++){
        if(!isVisted[i]){   // 해당 번호를 방문하지 않았다면
            isVisted[i] = true; // 방문
            arr[depth] = i; // arr에 저장
            permutation(arr, isVisted, N, M, depth + 1); // 재귀 함수 호출
            isVisted[i] = false; // 방문 해제 (중요!)
        }
    }

}