BaekJoon 15663번: N과 M (9)

풀이법

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

2) sort() 함수를 이용해서 오름차순으로 초기 배열을 정리해야 한다.

3) 중복에 함정이 존재한다. 이를 주의 해서 코딩해야 하며, 중복의 기준이 무엇인지 알아야 한다.

4) 같은 level의 직전의 함수와 새로운 값이 같으면 출력해서는 안된다.

추가 반례

입력 

3 3

1 1 2

출력

1 1 2

1 2 1

2 2 1

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, m;
vector<int> vec;
int arr[9];
bool visited[9];
void backtracking(int level)
{
	if (level == m)
	{
		for (int i = 0; i < m; i++)
		{
			cout << arr[i] << " ";
		}
		cout << "\n";
		return;
	}
	int temp = 0;//level이 올라갈때 마다 0으로 초기화 됨
	//level이 올랐을 때 출력되는 경우는 초기화 되지 않음
	for (int i = 0; i < vec.size(); i++)
	{
		if (visited[i])
		{
			continue;
		}
		if (temp== vec[i])
		{
			continue;
		}
		visited[i] = true;
		arr[level] = vec[i];
		temp = vec[i];
		backtracking(level + 1);
		visited[i] = false;
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		vec.push_back(a);
	}
	sort(vec.begin(), vec.end());
	backtracking(0);
}

한계점 및 개선사항 (+주의사항)

다른 N과 M문제와 비슷하지만, 여기서 point는 temp라는 변수이다.

백준에서 제공하는 다음과 같은 예제를 보자.

이 경우 temp변수를 사용하는 대신 if(arr[level]==vec[i]) 조건을 만나면 continue 하는 방식으로 풀어도 문제 없는 결과가 나온다.

허나 앞서 제공한 반례를 넣어보면 문제가 발생한다.

[1 1 2]  [1 2 1] 을 출력한 이후 level이 0으로 돌아가서 [2 1 1]을 출력하려고 할때 arr의 값 초기화 되지 않아 arr[2]가 1이라는 값을 가지고 있기에 [2 1 1]은 출력되지 못한다.

 

-> int temp=0; 을 선언하므로써 문제를 해결할 수 있었다.

재귀로 인해 level이 올랐으나 출력이 이뤄지는 level에 도달하지 못한 경우 temp는 0으로 초기화 된다.

level이 올랐을 때 출력되는 경우는 초기화 되지 않는다.

 

핵심은 같은 레벨에서 중복되는 값이 출력되서는 안된다는 것이다.

temp 변수를 이용한다면 level이 올랐을 때 출력되는 경우 temp가 초기화 되지 않기에

출력 level로 올라가기 전에 중복을 막을 수 있다.

- ex) [2 4 4] 의 경우 두 번째 4를 출력한 후 다시 for문으로 돌아왔을 때 세 번째 4는 temp 변수에 막혀 출력 되지 않게 할 수 있다.

- ex) 반례의 경우 [1 2 1] 출력 이후 [2 1 1] 출력 시 (2->1) 과정에서 (level이 오르고 출력은 안되는 경우) temp는 0으로 초기화 되기에 뒤에 1이 무사히 출력 되어 [2 1 1] 의 값이 나올 수 있다.

 

이해가 어렵다면 디버깅을 통해 직접 공부해 보는 것이 도움이 될 것이라 확신한다.

 

github.com/pearlcrum/CodingTest/tree/main

pearlcrum/CodingTest