백준 - 15649~15652 N과 M(1)~(4)

N과 M(1)

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

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

---

✔ 접근방법

DFS와 백트래킹으로 해결

1. DFS를 통해 수열을 출력하는 함수 작성
2. 탈출조건 cnt가 m가 같아지면 재귀호출에서 탈출
3. 중복방문을 체크하는 조건문을 이용하여 노드 탐색 횟수 감소

---

✔ 코드

#include <stdio.h>
#include <vector>

using namespace std;

int n,m;
int visit[10];  // 방문 노드 확인
vector<int> v;

void DFS(int cnt){
    // 출력
    if( cnt == m){
        for(int i=0; i<v.size(); i++){
            printf("%d ", v[i]);
        }
        printf("\n");
        return ;
    }
    // 재귀호출을 통한 DFS
    else{
        for(int i=1; i<=n; i++){
            // 중복 방문을 체크
            if(visit[i] != true){
                // 재귀호출 시 값 설정
                visit[i] = true;
                cnt++;
                v.push_back(i);

                DFS(cnt);
                
                // 호출종료 시 값 해제
                visit[i] = false;
                cnt--;
                v.pop_back();
            }
        }
    }
}

int main(void){
    
    int cnt = 0;
    scanf("%d %d", &n, &m);

    DFS(cnt);

    return 0;
}

---

☝ 팁

• 재귀함수는 코드는 간단해보이지만 정리하지 않고 작성하면 무한호출에 빠지게 된다. 계획한대로 한 스텝씩 작성하고, 탈출조건을 정확하게 정의한다.

• 상태공간트리와 백트래킹을 이용하면 쉽게 이해 가능

---

---

N과 M(2)

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
  - 고른 수열은 오름차순이어야 한다.

---

✔ 접근방법

유망함수를 수정하여 탐색횟를 줄인다.

4. 중복함수 체크 조건문에 이미 방문한 노드보다 작은 수는 탐색 안하는 조건을 추가

---

✔ 코드

#include <stdio.h>
#include <vector>

using namespace std;

int n,m;
int visit[10];  // 방문 노드 확인

void DFS(int cnt, int max){
    // 출력
    if( cnt == m){
        for(int i=0; i<v.size(); i++){
            printf("%d ", v[i]);
        }
        printf("\n");
        return ;
    }
    // 재귀호출을 통한 DFS
    else{
        for(int i=1; i<=n; i++){
            // 중복 방문을 체크 && 오름차순 방문 체크
            if(visit[i] != true && i > max){
                // 재귀호출 시 값 설정
                visit[i] = true;
                cnt++;
                v.push_back(i);
                max = i;

                DFS(cnt, max);
                
                // 호출종료 시 값 해제
                visit[i] = false;
                cnt--;
                v.pop_back();
            }
        }
    }
}

int main(void){
    
    int cnt = 0;
    int max = 0;    // 오름차순을 위한 변수 최대값 변수
    scanf("%d %d", &n, &m);

    DFS(cnt, max);

    return 0;
}

---

☝ 팁

• 재귀함수에 index의 위치를 저장할 변수를 추가로 전달한다.
• 재귀호출로 쌓이는 함수 호출스택에서 위에서 설정한 index 변수는 call by value로 사용된다.

---

---

N과 M(3)

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
  - 같은 수를 여러 번 골라도 된다.

---

✔ 접근방법

DFS와 백트래킹으로 해결

1. DFS를 통해 수열을 출력하는 함수 작성
2. 탈출조건 cnt가 m가 같아지면 재귀호출에서 탈출
   3. 중복방문을 체크하는 조건문을 이용하여 노드 탐색 횟수 감소

---

✔ 코드

#include <stdio.h>
#include <vector>

using namespace std;

int n,m;
int visit[10];  // 방문 노드 확인
vector<int> v;

void DFS(int cnt){
    // 출력
    if( cnt == m){
        for(int i=0; i<v.size(); i++){
            printf("%d ", v[i]);
        }
        printf("\n");
        return ;
    }
    // 재귀호출을 통한 DFS
    else{
        for(int i=1; i<=n; i++){
            // 재귀호출 시 값 설정
            visit[i] = true;
            cnt++;
            v.push_back(i);

            DFS(cnt);
            
            // 호출종료 시 값 해제
            visit[i] = false;
            cnt--;
            v.pop_back();
        }
    }
}

int main(void){
    
    int cnt = 0;
    scanf("%d %d", &n, &m);

    DFS(cnt);

    return 0;
}

---

☝ 팁

• 기본적인 형태의 DFS 문제이다. 이 원형을 가지고 조건을 추가하여 복잡한 DFS 문제를 해결 할 수 있을 것 같다.

---

---

N과 M(4)

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

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

---

✔ 접근방법

DFS와 백트래킹으로 해결

1. DFS를 통해 수열을 출력하는 함수 작성
2. 탈출조건 cnt가 m가 같아지면 재귀호출에서 탈출
   3. 중복방문을 체크하는 조건문을 이용하여 노드 탐색 횟수 감소

4-1. 비내림차순 조건을 추가

---

✔ 코드

#include <stdio.h>
#include <vector>

using namespace std;

int n,m;
vector<int> v;

void DFS(int cnt, int max){
    // 출력
    if( cnt == m){
        for(int i=0; i<v.size(); i++){
            printf("%d ", v[i]);
        }
        printf("\n");
        return ;
    }
    // 재귀호출을 통한 DFS
    else{
        for(int i=1; i<=n; i++){
            // 비내림차순 체크
            if(i >= max){
                // 재귀호출 시 값 설정
                cnt++;
                v.push_back(i);
                max = i;

                DFS(cnt, max);
                
                // 호출종료 시 값 해제
                cnt--;
                v.pop_back();
            }
        }
    }
}

int main(void){
    
    int cnt = 0;
    int max = 0;
    scanf("%d %d", &n, &m);

    DFS(cnt, max);

    return 0;
}

---

☝ 팁

• 오름차순 조건의 반대 경우를 생각한다.

---

👍 참고 사이트

백준 15649 문제
백준 15650 문제
백준 15651 문제
백준 15652 문제