[백준] 15649번 N과 M

 

 

문제

소스코드

#include<iostream>
#include<vector>
/*
N: 1부터 N까지
M: 중복이 없는 수열
*/
int g_N, g_M;
std::vector<int> g_v;
std::vector<bool> g_visited;

void BackTracking(int curr) {

	//curr이 4이면 출력
	if (curr > g_M) {
		for (const auto& i : g_v)
			std::cout << i << " ";
		std::cout << "\n";
		return;
	}

	//반복문을 사용한다 
	for (int i = 1; i <= g_N; ++i) {

		//현재노드가 true가 아니면 돈다. true이면 이미 방문했다.
		if (g_visited[i] != true) {
			g_visited[i] = true; 
			g_v.emplace_back(i);
			BackTracking(curr + 1); //카운터를 증가시킨다.
			g_v.pop_back();
			//리턴 후 돌아오는 부분
			g_visited[i] = false;
		}
	}
}


int main() {
	std::cin >> g_N >> g_M;
	g_visited.assign(g_N + 1, false);
	BackTracking(1); //0부터 시작
}

 

후기

이 문제를 해결하기 위한 키워드는 백트래킹과 수열이다.

 

수열이란 수를 늘어놓은 집합을 말하며 이 수는 규칙이 있어도 되고 없어도 된다. EX){1,2,3}, {3,5,7}

백트래킹이란 DFS구조를 가지는 방법 중 하나로 모든 경로를 찾는 방법 중 하나이다.

이 문제의 백트래킹 함수 부분의 작동을 시각화하면 다음과 같다. 

반복문 밑에 함수들은 모두 if밑에 있는 함수 들이며 오른쪽에 있는 그림은 해당 함수의 적용 후 모습이다.

 

먼저 함수를 시작 후 함수에 있는 반복문 index가 1인 경우의 모습이다. 이렇게 값을 담는 전역 변수(vector)와 방문 여부를

체크하는 전역 변수(visited)가 있으며 이 두 개는 vector 자료구조의 형태를 가진다. index 1이 flase 이기 때문에 1을 넣고 다시 함수를 호출하게 된다.

 

위의 단계에서 다시 호출한 함수의  index가 2인 경우의 모습이다. 다시 호출함 함수에서는 index 1이 True

상태 이기 때문에 index 2의 값이 값에 들어가게 된다.

위의 단계에서 다시 호출한 함수의  index가 4인 경우의 모습이다. 앞에 3이 들어가는 경우는 그림에서 생략을 하였다.

최종 모습은 옆의 그림과 같다.

 

이후 재귀함수 탈출 조건인 curr가 M보다 크기 때문에 지금까지 vector에 있던 모든 원소를 출력하고 함수를 리턴하게 된다. 이 이후의 그림은 리턴 후에 작동하는 모습이다.

BackTracking() 함수 이후에는 재귀 함수 특성상 FILO 형태이기 때문에 마지막으로 들어갔던 index 4인 상태의 함수로

오게 된다. 이후 가장 뒤에 있던 4를 vector와 visited에서 제거 및 false 처리를 하고 반복문 범위를 벗어나기 때문에

함수는 종료된다.

 

그 후 재귀 함수의 다음 스택인 index가 3인 상태의 함수로 오게 된다. 이 함수에서도 앞과 동일하게 3을 vector와 

visited에서 제거 및 false 처리를 하고 반복문이 아직 범위 안이기 때문에 한번 더 반복문을 돌게 된다.

반복문을 한번 더 돈 상태에서  index 4인 경우의 모습이다. 여기서는 4가 false 이기 때문에 4를 넣게 된다.

앞에서 3이 들어갔던 모습과는 다른 모습을 볼 수 있다. 그 후 다시 함수를 호출하게 된다.

 

앞의 index 1~2는 전부다 True 상태이기 때문에 넘어가고 3이 false 상태였기 때문에 3을 넣을 수 있고

3을 넣음과 동시에 True로 변환하고 다시 함수를 호출한다. 함수를 호출한 뒤에는 다시 curr가 M보다 

클 예정이기 때문에 위와 같은 반복을 하면서 중복이 없는 수열을 출력하게 된다.

 

 

백트래킹 문제를 처음으로 풀어보았다. 100% 내 힘으로는 풀지 못했다. 이러한 생각이 머리에서 떠오르지를 못했다.

다른 사람이 푼 문제를 이해하고 푸는 형태로 진행을 하였고 나 자신이 기억을 못 할 때를 대비해서 최대한 자세히 작성을 진행해 보았다.  다시 한번 느꼈지만 재귀 함수도 쉬운 게 아니다.

 

출처 및 레퍼런스

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

 

관련 글

[자료구조 알고리즘/탐색 알고리즘] - 백 트래킹(Backtracking)

[자료구조 알고리즘/탐색 알고리즘] - 깊이 우선 탐색(Depth First Search)