[백준 15650번] N과 M(2)

---

문제 화면

문제 링크 : https://www.acmicpc.net/problem/15650

문제 풀이

이 문제는 dfs를 사용해 백트래킹하는 문제이다.

기존의 N과 M(1) 문제와 동일하게 dfs로 백트래킹 하는 문제이지만 프린트배열에 방문 숫자를 추가할 때 현재 방문하는 숫자가 바로 전 숫자보다 더 큰지 여부를 확인하는 코드만 추가하면 된다.

제출 코드

#include <iostream>
using namespace std;

int visited[9] = {0, }; // 방문 여부를 저장하는 배열
int print[9] = {0, }; // 프린트할 목록을 저장하는 배열

int n, m;

void dfs(int k) {
  if (k==m) { // m개만큼 탐색한 경우 프린트할 목록에 담겨져 있는 숫자들을 프린트한다
    for(int i = 0 ; i < m ; i++) {
      cout << print[i] << " ";
    }
    cout << '\n';
  }

  else {
    for(int i = 1 ; i <= n ; i++) { // 모든 경우의 수 탐색
      if(!visited[i] && i > print[k-1]) { // 방문하지 않은 경우만 방문(중복 허용 x) + 증가수열이 되는지 확인
        visited[i] = 1; // 방문 표시
        print[k] = i; // 프린트 배열에 저장
        dfs(k+1); // 방문개수 +1 -> 계속 방문
        visited[i] = 0; // 프린트하고 리턴되었을 때 다음 방문을 위해서 방문표시 초기화
      }
    }
  }

}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  cin >> n >> m; // n과 m 입력 받기

  dfs(0); // dfs 함수 호출

  return 0;
} 

결론

이 문제는 dfs를 이용해 백트래킹을 할 수 있는지 묻는 간단한 문제이다. 로직은 어렵진 않지만 처음 하면 헤멜 수 있다고 생각한다.