백준 15649 N과 M (1)

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

 

서론

DFS와 백트래킹 문제

 

---

아이디어

n이 4이고 m이 2인 예제면

 

DFS를 이용해서 위 그림과 같이 모든 경우의 수를 출력하게 할 수 있다.

DFS함수는 반복문으로 1~n의 값을 가지는 DFS를 불러오고 DFS를 불러올 때마다 우측으로 자리수를 한자리씩 옮기도록 인덱스를 1씩 증가시켜주면 된다.

 

그런데 문제에서 중복없이 출력하라는 조건을 줬기 떄문에

우측으로 인덱스가 증가할때마다 선택된 값은 방문처리해주고 만약 방문처리 된 값을 다시 접근하면 그대로 리턴시킨다. 

 

---

구현

//c++

#pragma warning(disable:4996)
#include <iostream>
#include <cstdio>

int n, m;
int visited[9];
int seq[9];

void dfs(int value, int idx) {
	//std::cout << value << " " << idx << std::endl;
	if (visited[value] == 1) return;

	seq[idx] = value;

	if (idx == m) {
		for (int i = 1; i <= m; i++) printf("%d ", seq[i]);
		printf("\n");
		return;
	}

	visited[value] = 1;
	for (int i = 1; i <= n; i++) {
		dfs(i, idx + 1);
	}
	visited[value] = 0;
	return;
}

int main() {
	scanf("%d %d", &n, &m);
	dfs(0, 0);
}