득이공간
[백준 C++] 15649 N과 M (1) - 백트래킹 본문
#include <iostream>
using namespace std;
int N, M;
bool Visit[8];
int Seq[8];
void Print()
{
for (int i = 0; i < M; ++i)
{
cout << Seq[i] + 1 << ' ';
}
cout << '\n';
}
void DFS(int CurIdx)
{
if (CurIdx == M)
{
Print();
return;
}
for (int i = 0; i < N; ++i)
{
if (Visit[i])
{
continue;
}
Seq[CurIdx] = i;
Visit[i] = true;
DFS(CurIdx + 1);
Visit[i] = false;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> N >> M;
DFS(0);
}
DFS & 백트래킹 문제입니다.
중복없이 M개를 고른 수열을 출력해야하기 때문에
방문 체크 배열을 따로 관리하면서 각 경우를 탐색하도록 했습니다.
'PS > 알고리즘 문제풀이' 카테고리의 다른 글
[백준 C++] 1043 거짓말 - 분리집합 (0) | 2024.03.04 |
---|---|
[백준 C++] 17070 파이프 옮기기 1 - 다이나믹프로그래밍 (0) | 2024.03.04 |
[백준 C++] 15686 치킨 배달 - 브루트포스 (0) | 2024.03.03 |
[백준 C++] 12865 평범한 배낭 - 다이나믹프로그래밍 (0) | 2024.03.03 |
[백준 C++] 5639 이진 검색 트리 - 트리 (0) | 2024.02.29 |