BaekJoon 15649번: N과 M(1)

간단한 문제지만 BackTracking을 사용하지 않는 경우 생각보다 시간이 오래 걸린다.

 

풀이법

1) 재귀 함수를 이용하여 level에 도달하게 되면 출력하는 형식으로 BackTracking을 구현한다.

2) 방문한 곳을 다시 방문하지 않기 위한 visited 배열과 각 level의 값을 담을 수 있는 arr 배열을

   생각해 낸다면 어렵지 않게 풀 수 있는 문제이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, m;
int arr[9];
bool visited[9];
void dfs(int level)
{
	if (level == m)// 원하는 level에서 출력할 것
	{
		for (int i = 0; i < m; i++)
		{
			cout<<arr[i] << " ";
		}
		cout << "\n";
		return;
	}
	for (int i = 1; i <= n; i++)
	{
		if (visited[i])
		{
			continue;
		}
		visited[i] = true;
		arr[level] = i;
		dfs(level + 1);
		visited[i] = false;
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n>>m;
	dfs(0);
	
}

한계점 및 개선사항

한 동안 풀지 않던 BackTracking 문제를 만나서 시간이 오래 걸렸다. 랜덤하게 문제를 골라 어떤 방식으로 해결해야 할지 스스로 고민하는 시간을 늘리는 방향으로 준비를 해 나가야 할 것 같다.

 

github.com/pearlcrum/CodingTest/tree/main

pearlcrum/CodingTest