[백준 15649번] N과 M (1)
Updated:
개요
백준 15649번 문제이다. 퇴각 검색(backtracking)을 활용해 보기 좋은 문제 중 어렵지 않은 문제이다.
사실 금방 풀 수 있었지만 아직 연습이 부족해 많은 시간을 소요해 버렸다. 애초에 처음으로 풀어보는(뭐든지 지금은 처음이겠지만…) 백트래킹 문제였다 ㅋㅋㅋ…
문제
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
접근
백트래킹 입문자로서 문제를 어떻게 풀어야 할지 감이 안 잡혀서 구글링을 해 보았더니, 백트래킹을 트리로 설명하는 사진을 보고 recursion으로 풀어보면 되지 않을까는 생각을 하게 되었다.
list나 array를 만들어서(list로 풀었지만, array로 푸는 것이 더 좋을 것 같다), 첫번째 자리 수를 1에서 N까지 하나씩 넣어 본다. 이 때 다른 자리수와 중복되지 않았으면(첫번째에서는 애초에 다른 자리 수가 아직 없기 때문에 이 명제는 항상 참이다.) list에 그 수를 맨 뒤에 넣어 두고, 다음 자리 수로 넘어간다. 그리고 두번째 자리 수에서 1에서 N까지 하나씩 넣어 보고, 중복되지 않았으면 다음 자리 수로 간다.
이런 식으로 반복하다 어떤 자리수에서 탐색을 끝냈으면(1에서 N까지 모두 살펴 보았으면) 하나 윗자리로 돌아가서 다시 다른 수를 탐색한다.
만약 모든 자리수를 다 채웠다면 그 수를 모두 출력하고 그 다음 수부터 다시 탐색을 하게 된다.
이를 구현하기 위해 recursion을 사용했다. 중복되는 수가 없으면 그 수를 리스트 맨 뒤에 집어넣고 l(자리수를 의미)을 1 증가시켜서 자기 자신을 다시 호출한다. 그리고 탐색이 끝났으면 그 앞자리 수를 빼내고 함수를 끝낸다.
만약 모든 자리수를 다 찾았다면 출력하고 마지막 자리수를 뺀 다음 다시 탐색을 한다.
void search_seq(int l)
{
if (l >= m)
{
list<int>::iterator curr = seq.begin();
for (int i = 0; i < m; i++)
{
cout << *curr << ' ';
curr++;
}
cout << '\n';
seq.pop_back();
return;
}
for (int i = 1; i <= n; i++)
{
if (check_num(i))
{
seq.push_back(i);
search_seq(l + 1);
}
}
if (!seq.empty())
seq.pop_back();
}
여기서 check_num이라는 함수를 새로 만들었는데, 중복 여부를 체크해주는 함수다.
bool check_num(int n)
{
list<int>::iterator curr = seq.begin();
for (int i = 0; i < seq.size(); i++)
{
if (n == *curr)
return false;
curr++;
}
return true;
}
문제를 푼 이후 인터넷을 찾아보니, 이러한 방식을 DFS(깊이 우선 탐색)라고 한다.
루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
- 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.
- 즉, 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것이다.
- 사용하는 경우: 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택한다.
- 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단하다.
- 단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다.
위의 내용은 어떤 블로그(아래에 주소 있음)에서 인용한 것으로, 정리하자면 DFS는 깊게 먼저 파고드는 탐색이다.
소스코드
#include <bits/stdc++.h>
using namespace std;
int n, m;
list<int> seq;
bool check_num(int n)
{
list<int>::iterator curr = seq.begin();
for (int i = 0; i < seq.size(); i++)
{
if (n == *curr)
return false;
curr++;
}
return true;
}
void search_seq(int l)
{
if (l >= m)
{
list<int>::iterator curr = seq.begin();
for (int i = 0; i < m; i++)
{
cout << *curr << ' ';
curr++;
}
cout << '\n';
seq.pop_back();
return;
}
for (int i = 1; i <= n; i++)
{
if (check_num(i))
{
seq.push_back(i);
search_seq(l + 1);
}
}
if (!seq.empty())
seq.pop_back();
}
int main()
{
cin.tie(NULL);
ios::sync_with_stdio(false);
cin >> n >> m;
search_seq(0);
return 0;
}
후기
recursion을 사용한 알고리즘을 설명하기가 생각보다 어려웠던 것 같다. 그래서 접근 부분이 장황해진 감이 없진 않다.
이 문제를 풀면서 느낀 것은 연습이 많이 필요할 것 같다는 것이다. 결국 연습을 통해 익숙해져야 더 어려운 문제도 풀 수 있을 것이고, 시간단축도 될 것이다.
Leave a comment