[Baekjoon] 15649번: N과 M (1)

https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

 

---

 

문제 해결 과정

착안

주어지는 입력 \(N\), \(M\)에 따라 \(N\) 개의 정점을 가지는 그래프를 만든 다음, 각 정점에 대하여 인접 정점을 오름차순으로 방문 가능하도록 자신을 제외한 모든 정점들과 연결한다. 만들어진 그래프로부터 \(M\) 개의 정점이 순회될 수 있는 모든 경로를 순서대로 출력하기 위하여 백트래킹(backtracking, 퇴각검색) 알고리즘을 구현하고자 하였다.

 

// 의사 코드
void MoveTo(int NUMBER)
{
	visited[NUMBER] = true;
	//TODO: Add NUMBER to SEQUENCE
    
	for (int i = 1 to N)
		if ((i is not VISITED) and (length(SEQUENCE) < M))
			MoveTo(i);
	
	if (length(SEQUENCE) = M)
		// TODO: Print SEQUENCE

	//TODO: Trace back
}

void FindSequence()
{
	for (int start = 1 to N)
		MoveTo(start);
}

 

사실상 깊이 우선 탐색(DFS) 알고리즘과 크게 차이나는 부분은 없으나(재귀를 통해 구현하므로) 원하는 깊이 \(M\)까지의 탐색을 완료했을 때 탐색을 종료하는 것이 아니라, 다시 한 단계씩 trace back 하여 나머지 모든 가능한 경로에 대해서도 전부 탐색을 하는 방식으로 백트래킹 알고리즘을 구현하고자 하였다.

 

구현

그래프에서 재귀를 통해 정점을 순회하는 것과 같이 구현하여 문제를 해결할 수 있으나, 편의상 굳이 정점을 만들지 않고 bool 형의 배열과 수열을 저장할 int 형의 배열만 있어도 구현이 가능하였기 때문에 실제 그래프 구조처럼 정점 등을 굳이 만들지 않고 보다 간단하게 단순화한 클래스와, 그에 따른 멤버 함수 형태로 백트래킹 알고리즘을 구현하였다(전역 변수를 쓰기 싫어서 굳이 클래스로 만든 것).

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>
#include <vector>

using namespace std;

class SequenceGenerator
{
public:
	SequenceGenerator(int n, int m) : N(n), M(m) {}

	void PrintSequence()
	{
		printf("%d", Sequence[0]);

		for (int i = 1; i < M; i++)
			printf(" %d", Sequence[i]);

		printf("\n");
	}

	void NextTerm(int num, int term)
	{
		Visited[num - 1] = true;
		Sequence[term++ - 1] = num;
			
		for (int i = 1; i <= N; i++)
			if (!Visited[i - 1] && term <= M) NextTerm(i, term);

		if (term > M)
			PrintSequence();

		Visited[Sequence[--term - 1] - 1] = false;
	}

	void FindSequences()
	{
		for (int i = 1; i <= N; i++)
			NextTerm(i, 1);
	}

private:
	const int N, M;
	bool Visited[8] = { false, };
	int Sequence[8];
};

int main()
{
	int N, M;
	scanf("%d %d", &N, &M);

	SequenceGenerator seq(N, M);
	seq.FindSequences();
	
	return 0;
}

 

실행 결과

수 많은 실행 속도 단축 시도에도 불구하고 그냥 코드의 길이만 짧아졌을 뿐이다(처음엔 진짜 아예 그래프로 구현함)... ㅠ_______ㅠ