[백준 15649번] N과 M(1)

---

문제 화면

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

문제 풀이

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

가능한 모든 조합을 사용하기 위해서는 모든 케이스를 탐색하는 로직을 짜야 하기 때문에 bfs나 dfs가 적합한데 출력 예시를 보면 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]) { // 방문하지 않은 경우만 방문(중복 허용 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를 이용해 백트래킹을 할 수 있는지 묻는 간단한 문제이다. 로직은 어렵진 않지만 처음 하면 헤멜 수 있다고 생각한다.