[BOJ] 15649번. N과 M(1)

문제 1. N과 M(1)

www.acmicpc.net/problem/15649

15649번: N과 M (1)

백트래킹을 사용하여 풀 수 있는 문제입니다. 코드를 설명하기 앞서, 백트래킹이 무엇인지 살펴보겠습니다.

 

[백트래킹]

모든 경우를 방문하지만, 규칙을 가지고 방문하지 않아도 될 노드는 방문하지 않는 알고리즘입니다. 해당 노드의 답이 될 수 있는 가능성을 따져보고,  답이 될 수 있는 가능성이 있다면 계속 진행, 그렇지 않다면 부모노드로 돌아가 탐색을 계속합니다. 

우리는 이미 이 알고리즘을 잘 알고 있습니다. 위의 설명이 이해가 되지 않으신다면, 다음과 같은 예제는 어떤가요?

 

친구와 오목을 하고 있다고 생각해 봅시다.

당신은 흰돌, 친구는 검은돌입니다.

그런데...

앗... 검은 돌이 대각으로 3개를 만들었는데 내 이익에 눈이 멀어 놓치고 말았습니다. 꼼짝없이 지게 생겼죠.

하지만 당신은 힘이 친구보다 힘이 셉니다.

 

당신: 야 한번만 무르자...

친구: 아 응...

 

뒤로 되돌아가 아까했던 실수를 반복하지 않고 최적의 수를 찾았습니다. 결국 친구가 이길것 같긴 하지만, 그때마다 무르면 됩니다. 앞으로 누구도 당신과 오목을 하고 싶어하지 않을거에요. 하지만 괜찮습니다. 이기면 장땡입니다.

 

우리는 백트래킹을 대충 알 것 같습니다. 그럼 이 문제에 백트래킹을 어떻게 적용시킬지 살펴보겠습니다.

 

[백트래킹 문제에 적용시키기 - 예제와 함께]

N=3, M=3이라고 가정하겠습니다.

우리는 3칸짜리 출력을 해야 하므로 다음과 같이 태초에 빈 세칸짜리 네모가 있다고 생각해봅시다.

 

 

왼쪽부터 차례대로, 문제가 요구했던 것 처럼 숫자를 채워보겠습니다. 언제까지? 세칸이 모두 다 찰때까지요. 다음과 같이 트리가 꽉 차면, 당신은 결정해야합니다.

우선 123의 목표는 채웠으니 출력합니다(대부분의 코딩 테스트에서, 출력이 생길때마다 출력해도 괜찮습니다!). 

다만 세칸을 모두 채웠으므로, 부모에게 돌아가 새로운 자식을 만들 수 있는지 물어봅니다. 하지만 12□(부모노드)의 입장에서는 더이상 해줄게 없습니다. 부모의 부모 노드로 올라가 자식을 만들어봅니다.

다음과 같은 과정을 통해, 우리는 132를 또 출력할 수 있었습니다. 그럼 우리는 맨 앞 숫자가 1인 모든 경우의 수를 출력한 것 같습니다. 그럼, 맨앞 노드가 2인 경우에도, 3인 경우에도 모든 수열을 출력할 수 있지 않을까요? 그럼 코드를 살펴보겠습니다(트리 다 그리기 귀찮은거 아닙니다).

 

[백트래킹 적용시키기 - 코드와 함께]

#include <iostream>
using namespace std;

int n, m;
int field[9], visited[9] = { 0, };

void back_tracked(int num);
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	back_tracked(0);
	return 0;
}

void back_tracked(int num)
{
	if (num == m)
	{
		for (int i = 0; i < m; i++)	cout << field[i]<<" ";
		cout << "\n";
		return;
	}
	else
	{
		for (int i = 1; i <= n; i++)
		{
			if (!visited[i])
			{
				visited[i] = 1;
				field[num] = i;
				back_tracked(num + 1);
				visited[i] = 0;
			}
		}
	}
}

제가 변수명 짓는 센스가 없습니다...

field는 위에 그림에서 설명한 빈 칸과 같습니다.

visited는 어떠한 숫자 혹은 배열을 방문 했었는지 잠시 기억하는 배열입니다. 자주쓰이니, 알아두시면 좋은 스킬입니다.

 

main입니다. 위에 두 줄은, 무시하셔도 됩니다. 출력이 어마무시하게 많거나 입력이 많을 경우 넣어주는 코드입니다.

 

n과 m을 입력받아 바로 back_tracked함수에 인자 0을 넣어주는 모습을 볼 수 있습니다.

그림을 그려보며 직접 visited와 field의 변화를 썼다 지우며 코드가 돌아가는 모습을 확인해보세요.

간략하게 설명하자면,  첫번째 if(cnt==m)부분에서 빈칸이 모두 채워졌는지 확인하고, 자신을 부른 함수에 재귀적으로 돌아가 마지막 원소가 채워지기 직전의 상태로 되돌아가게 됩니다.