백준 N과 M (2), (5), (9)

베이스 코드가 유사해 하나로 묶어서 작성한다.

 

N과 M (2) : https://www.acmicpc.net/problem/15650

 

N과 M (5) : https://www.acmicpc.net/problem/15654

 

N과 M (9) : https://www.acmicpc.net/problem/15663

 

백트래킹 기법으로 구현하라는데, 재귀 함수를 사용하면 된다.

다음의 재귀함수 패턴에서, 문제의 요구사항에 따라 약간의 조정을 가하자.

int visited[8] = { 0, };
vector<int> v;

int main() {
	ios_base::sync_with_stdio(false);
	cout.tie(0);
    /* 입력받기 */
    recursion(n, m, vector<int> ());
}

void recursion(int n, int m, vector<int> res) {
	if (m == 0) {
		/* res 원소 하나씩 출력 */
        return;
	}
    
	for (int i = 0; i < n; i++) {
		if (!visited[i]) {
			res.push_back(v[i]); visited[i] = 1;
			recursion(n, m - 1, res);
			res.pop_back(); visited[i] = 0;
		}
	}
}

 

 

res는 수열을 저장하는 배열, visited는 순회에 사용할 배열이다.

 

입력받은 배열 전체를 순회하면서, 아직 방문하지 않은 인덱스 i가 있다면 원소 v[i]를 수열에 추가하고 해당 인덱스를 방문했다고 표시한다. 이렇게 하면 재귀호출을 통해 다음 recursion을 수행하는 중에는 i번 원소가 표시되어있으므로 v[i]를 다시 수열에 넣지 않을 수 있다.

 

대신 재귀호출을 마치고 함수 밖으로 나오면 res에서 v[i]를 제거하고 visited에 한 표시도 지운다. 즉, res와 visited를 반복문을 수행하기 전 상태로 복구해, 다음 loop를 수행할 때 영향이 가지 않도록 해야 한다.

 

처음 재귀함수를 공부할 때는, 개념은 뭔가 알 거 같은데 실제로 구현해보려면 엄청 헷갈린다. '키고 들어갔다가 나와서 끄기'라고 직관적으로 받아들여보면 좀 더 낫지 않을까 싶다.

 

문제 (2)는 수열 v의 수를 따로 입력받지 않으므로 v에 1~n까지의 자연수를 저장해 실행하면 된다.

문제 (5)는 수열의 출력 순서를 오름차순으로 하기 위해 수열 v를 오름차순으로 정렬해야 한다. 이게 이해가 잘 되지 않으면 직접 종이에 표시해가며 재귀함수의 수행 과정을 따라가보자.

문제 (9)는 (5)의 조건에 더해 배열의 원소에 중복이 존재한다. 다른 풀이도 있겠지만 나는 repeated 배열을 추가했다.

//예시
//v : [1, 3, 4, 4, 6]
//repeated : [0, 0, 0, 1, 0]

 

v를 정렬한 뒤 원소를 스캔하며 현재 원소와 앞 원소가 동일할 경우 repeated 값을 1로 한다. 그리고 반복문에서 res와 visited를 복구한 뒤 다음의 코드를 추가했다.

 

for (i; i < n && repeated[i + 1]; i++);

이렇게 하면 중복되는 원소에서의 재귀호출을 막을 수 있다.

 

참고로 입력 수열에 대해 문제 (2)는 조합, 문제 (5)는 순열, 문제 (9)는 중복순열이 출력된다.

이때 순열의 경우 최대 8P8 = 8! = 40,320 번의 출력이 발생하므로 시간초과를 막으려면 cout.tie(0)을 사용하자.

 

배운 내용

재귀함수 이용 백트래킹