[모의 테스트 풀이] N과 M(1)
두번째 풀이를 시작하겠습니다!
문제 1. N과 M(1)
15649번: N과 M (1)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
백트래킹을 사용하여 풀 수 있는 문제입니다. 코드를 설명하기 앞서, 백트래킹이 무엇인지 살펴보겠습니다.
[백트래킹]
모든 경우를 방문하지만, 규칙을 가지고 방문하지 않아도 될 노드는 방문하지 않는 알고리즘입니다. 해당 노드의 답이 될 수 있는 가능성을 따져보고, 답이 될 수 있는 가능성이 있다면 계속 진행, 그렇지 않다면 부모노드로 돌아가 탐색을 계속합니다.
우리는 이미 이 알고리즘을 잘 알고 있습니다. 위의 설명이 이해가 되지 않으신다면, 다음과 같은 예제는 어떤가요?
친구와 오목을 하고 있다고 생각해 봅시다.
당신은 흰돌, 친구는 검은돌입니다.
그런데...
앗... 검은 돌이 대각으로 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)부분에서 빈칸이 모두 채워졌는지 확인하고, 자신을 부른 함수에 재귀적으로 돌아가 마지막 원소가 채워지기 직전의 상태로 되돌아가게 됩니다.
그럼, 다음 문제로 가볼까요??