[BOJ] 백준 문제풀이 15649 N과M(1)

알고리즘 스터디 :

DFS와 BFS 기초를 다지기 위해서 쉬운 문제 부터 하나하나 차근차근 접근 해보려고 합니다. 

종만북은 문제 풀이로 병행을 하려하고, 나머지는 이제 하나하나 볼 것입니다. 

우선, DFS 문제를 푸려고 하는데, 

제 코딩 스타일이 알고리즘에 최적화 되있지 않다고 조언을 들었습니다. 시간 단축과 알고리즘 구현 단순화를 위해서

STL을 같이 공부할거에요.

암튼 ... 아래 문제를 풀었습니다. 

N과 M (1) 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	512 MB	1294	804	572	65.148%

문제

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

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

입력

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

출력

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

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

예제 입력 1 

3 1

예제 출력 1 

1
2
3

예제 입력 2 

4 2

예제 출력 2 

1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3

평소 접하던 DFS 조합 문제가 아닌 순열 문제 이며, 이 부분을 어떻게 풀 것인지 대해서 생각해 봤어요.

단순화를 위해서 Memset 함수를 사용하고, Vector 를 사용 했어요. 

1. Memset --> 특정 메모리 블럭에 특정 크기 만큼, 특정 문자로 셋팅하는 함수죠.

* 헤더 파일은 : memory.h 과 string.h 둘 중에 아무거나 사용해도 상관 없습니다. 

** memmove 는 string.h 에만 존재 하내요.

2. Vector --> 동적 배열을 C++ 로 구현한 함수죠. 

특징은 [] 연산으로 배열 위치에 접근할 수 있고, 그냥 배열처럼 삭제하고 삽입할 수 있습니다. 

* #include <vector> 를 선언해줘야 합니다. 

( 문제가 안풀렸었는데, 가르침을 받고 다시 작성 해봤음.)

3 - 1. 각 인자에서 전체 숫자에 접근 재귀

3 - 2. 방문 했던 인자를 체크

3 - 3. 방문 하지 않았던 인자만 사용

3 - 4. 방문 할때 마다 전역 변수와 배열을 벡터에 셋팅

3 - 5. 원하는 N 에 도달 했을때 출력 

#include <iostream>
#include <cstdio>
#include <vector>
#include <string.h>
 
using namespace std;
 
int ar[9] = {0,};
int M,N,cnt = 0; // 전역 변수에서 카운트
vector <int> li; // 벡터 사용
 
void dfs(){
    if(cnt == N){
        for(int i = 0; i<(int)li.size(); i++){ // 벡터 사이즈 만큼 출력 (정수) 변환
            printf("%d ", li.at(i));
        }
        printf("\n");
        return;
    }
    
    for(int i=0; i<M; i++){
        if(ar[i] == 1) continue; // 같은 인자는 패스
        ar[i] = 1;
        li.push_back(i+1); // 출력을 위한 기록으로 생각함.
        cnt++;
        dfs();
        ar[i] = 0;
        li.pop_back();
        cnt--;
    }
}
 
int main(){
    cnt = 0;
    memset(ar,0,sizeof(ar));
    li.clear();
    cin >> M >> N;
    dfs();
}
 
 

이렇게 코드를 작성 했는데, PASS 되었다.. 재귀 함수의 for문이 조금 더럽지만,,, 다른 문제도 풀어야 하기 때문에 정리하는것은 넘어갈게요