흔한 수열 문제
-
유형
문제 요약
-
네트워크 플로우, 이분 매칭,최대 유량주어진 조건을 만족하는 수열을 찾으세요.
※이 설명은 공식 솔루션이 아닌 작성자의 개인적인 솔루션입니다.
이 문제는 일단 풀고난 다음 굉장한 보람을 느꼈습니다. 그 이유는 아래 사진을 보면 됩니다.
알고리즘을 본격적으로 공부한 것은 2015년 이고, 군대 가기 전에 깔짝 대던 것은 2012년 부터였는데, 이 때는 이걸 풀면서 정말 나는 평생 이런 문제를 못 풀거라고 생각했습니다. 그리고 우연한 기회에 이걸 틀렸던 것을 확인하여 이번에 해결하였습니다.
이 문제는 1 x y z 또는 2 x y z 의 형태로 인풋이 주어지는데, 1이 올 경우 x~y번째의 수 중 가장 큰 것은 z이며, 2가 오면 그 반대가 됩니다. 그러므로 그 조건과 반대가 되는 수와 장소는 모두 숫자를 올 수 없다고 체크를 합니다. 예를 들어 1~4로 이루어진 수열이 있을 때, 1 1 3 2 가 왔다고 하면 1~3번째 위치에는 3,4과 올 수 없으며, 4번째 장소에는 2가 올수 없으므로 이를 올 수 없다고 처리합니다.
그 다음, 올 수 있는 부분을 모두 그래프로 연결해 줍니다. 이 문제는 한 자리에 숫자가 1개씩 들어가면 되므로 유량이 1인 네트워크 플로우 문제가 되며, 이를 최대 이분 매칭으로 변형하여 풀 수 있습니다. 이 때, 매칭이 되는 최댓값이 항상 n과 같아야 모든 자리에 수열의 원소가 들어간 것이므로, 들어가지 못했다면 -1, 들어갔다면 저장한 숫자를 출력해주면 됩니다.
클릭하여 소스코드 보기
※해당 소스코드는 참고용이며, 최적화 된 공식 솔루션 소스가 아닙니다. 이 소스를 그대로 복사하여 이용, 또는 제출하는 행위에 대한 불이익은 책임지지 않습니다.
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
bool a[201][201], visited[201];
int match[201], bm[201];
vector<vector<int> > v;
bool bpm(int n)
{
if (visited[n]) return false;
visited[n] = true;
for (auto it : v[n])
{
if (match[it] == -1 || bpm(match[it]))
{
match[it] = n;
bm[n] = it;
return true;
}
}
return false;
}
int main()
{
ios::sync_with_stdio(false);
int n, m;
cin >> n >> m;
v.resize(n + 1);
//a : [place][no]
for (int i = 0; i < m; i++)
{
int c, x, y, z;
cin >> c >> x >> y >> z;
if (c == 1)
{
for (int j = x; j <= y; j++)
for (int k = z + 1; k <= n; k++)
a[j][k] = true;
}
else
{
for (int j = x; j <= y; j++)
for (int k = 1; k < z; k++)
a[j][k] = true;
}
for (int j = 1; j < x; j++) a[j][z] = true;
for (int j = y + 1; j <= n; j++) a[j][z] = true;
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (!a[i][j])
v[i].push_back(j);
fill(match, match + n + 1, -1);
int cmp = 0;
for (int i = 1; i <= n; i++)
{
fill(visited, visited + n + 1, false);
if (bpm(i)) cmp++;
}
if (cmp != n) cout << "-1\n";
else
for (int i = 1; i <= n; i++) cout << bm[i] << " ";
}