[백준 알고리즘] 15649번 : N과 M (1), c++

https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

c++로 백준 15649번 문제를 풀어보겠다.

 

 

 

 

 

문제

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

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

입력

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

출력

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

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

예제 입력 1 복사

3 1

예제 출력 1 복사

1
2
3

 

 

 

 

 

<문제 풀이>

1. N, M, 순열을 저장할 배열, 방문한 숫자를 저장할 배열을 선언한다.

2. dfs를 위한 새로운 함수를 선언한다.

(원하는 만큼 숫자를 방문해 하나의 순열을 완성했다면, 하나씩 출력한다.)

(visited 배열을 사용해 숫자를 방문하며 순열을 만들어 배열에 저장한다.)

3. main 함수에서 N, M을 입력받은 후 dfs함수를 실행한다.

 

 

 

코드는 다음과 같다.

 

 

 

이 문제를 통해 알게 된 점 : 

순열을 생성할 때 DFS 함수를 활용해 해결할 수 있다는 것을 알게 되었다.

DFS를 사용하면 더 간단하고 빠른 코드를 작성할 수 있다는 것을 알게되었다.

DFS를 처음 구현해보았고 코드를 처음 작성해보았는데 이 코드가 익숙해 질 수 있도록 비슷한 문제들을 더 풀어봐야겠다는 생각이 들었다.

DFS 함수안에 재귀함수를 사용해 원할 때까지 실행되도록 할 수 있다.