쭉 순회하며 같은 색상에 대해 같은 Component를 이루도록하고 그 중 가장 큰 Component를 골라내면 된다.
#include <vector>
#include <queue>
using namespace std;
struct _d { int y, x;};
vector<int> solution(int m, int n, vector<vector<int>> picture) {
int number_of_area = 0;
int max_size_of_one_area = 0;
int i,j,vi[100][100] ={},dy[] = { 0, 0, 1, -1}, dx[] = {1, -1, 0, 0}, tmp_size;
queue<_d> q;
for(i=0; i<m;i++) for(j=0;j<n;j++) if(picture[i][j] && !vi[i][j]) {
q.push(_d{i,j});
number_of_area++;
tmp_size = vi[i][j] = 1;
while(!q.empty()){
_d u = q.front(); q.pop();
for(int k = 0; k < 4; k++) {
int ty = u.y + dy[k], tx = u.x + dx[k];
if(0 <= ty && ty < m && 0 <= tx && tx < n && !vi[ty][tx] && picture[ty][tx] == picture[u.y][u.x]){
q.push(_d{ty,tx});
vi[ty][tx] = 1;
tmp_size++;
}
}
}
max_size_of_one_area = max_size_of_one_area > tmp_size ? max_size_of_one_area : tmp_size;
}
vector<int> answer(2);
answer[0] = number_of_area;
answer[1] = max_size_of_one_area;
return answer;
}
2. 브라이언의 고민(TODO)
3. 4단 고음
[해설, 분류 - 완전탐색] O(???)
Greedy하게 생각해보자. 반드시 3단 고음의 형식을 유지하기 위해서는 반드시 맨 앞에는 '*'이 와야하며, 맨 뒤에는 '++'가 있어야만 한다.
따라서 이 규칙을 토대로 구성된 문자열을 역추적해가며 전체탐색을 진행하면 간단하게 구현할 수 있다.
처음 음역 1로 시작해서 n을 만드는 것이기 때문에, n을 3으로 나누거나 1을 빼서 1을 만들 수 있으면 답이 하나 증가하는 것이다.
여기서 1을 빼는 과정에서 전체탐색을 하면 무조건 시간 초과가 나기 때문에 반드시 가지치기를 해줘야 한다.
1을 빼는 것은 +의 개수를 증가시키는 것을 의미한다. 이는 곧 *++ 형태에서 +의 개수는 *의 두 배가 되며 규칙에 맞게 문자열을 배치했다면 이 등호는 반드시 성립한다.
따라서 +문자를 증가시킬 때 마다 가능한 *의 개수의 2배가 +의 개수를 넘어설 수 없다면 +의 수가 너무 많은 것이므로 앞으로 더 이상 진행할 필요가 없다.
#include <cstdio>
#include <cmath>
int brute(int n, int r) {
if (n < 1 || 2*log(n)/log(3) < r) return 0;
if (n == 3) return r == 2;
int ret = 0;
if (n % 3 == 0 && r >= 2)
ret += brute(n / 3, r - 2);
ret += brute(n - 1, r + 1);
return ret;
}
int solution(int n) {
int answer = 0;
answer = brute(n - 2, 2);
return answer;
}
4. 보행자 천국
기본 2차원 DP에서 조건을 추가한 문제다. 이런 류의 문제를 풀어본 적이 있다면 크기 거부감이 느끼지 않고 풀 수 있을 것 같다.
[해설, 분류 - Dynamic programming ]
추가된 상태는 통행 금지, 직진이다.
직진을 생각해보면 왼쪽 열에서 오든지 윗행에서 오든지 둘 중 하나이기 때문에 따로 '공간'을 잡아서 구분하도록 한다.
이런 공간을 구분한 상태에서, 통행 금지의 경우 바로 왼쪽열 또는 바로 윗행에서 오는 값을 받지 않으면 된다. 직진의 경우 왼쪽 열에서 온 값을 왼쪽에만, 윗행에서 온 값을 위에만 저장하도록 구현하면 된다.
#include <cstdio>
#include <vector>
using namespace std;
int MOD = 20170805;
const int MAX_NM = 500;
int solution(int m, int n, vector<vector<int>> city_map) {
int answer = 0, i, j, k, dp[MAX_NM][MAX_NM][2] = {};
dp[0][0][1] = dp[0][0][0] = 1;
for (i = 0; i<m; i++) {
for (j = 0; j<n; j++) {
if (!i && !j) continue;
if (city_map[i][j] == 1) continue;
if (i >= 1) dp[i][j][0] += dp[i - 1][j][0];
if (j >= 1) dp[i][j][1] += dp[i][j - 1][1];
dp[i][j][0] %= MOD, dp[i][j][1] %= MOD;
if (city_map[i][j] == 0) {
if (j >= 1) dp[i][j][0] += dp[i][j - 1][1];
if (i >= 1) dp[i][j][1] += dp[i - 1][j][0];
dp[i][j][0] %= MOD, dp[i][j][1] %= MOD;
}
}
}
return answer = (dp[m - 2][n - 1][0] + dp[m - 1][n - 2][1]) % MOD;
}
5. 캠핑
이런 알고리즘을 섞는 문제는 각각 분리해서 접근해면 쉬울지 몰라도 생각이 안나서 못 풀 때도 있다. 뭐랄까 답은 계속 꾸준히 많이 푸는 방법뿐인 것 같다..
[해설, 분류 - Grid compression, Prefix sum] O(n^2)
두 쐐기 A,B로 텐트를 쳐지기 위해서는 영역이 1이상, 그리고 그 경계선을 제외한 내부 사각형 영역에 다른 쐐기가 있어선 안된다.
먼저 두 쐐기를 고르는 과정은 O(n^2)으로 시간도 충분하다. 또 영역 1이상을 확인하는 과정도 O(1)로 판단할 수 있다. 그렇다면 내부 사각형 영역에 쐐기가 있는지를 판단하는 과정이 필요하게 된다.
내부 사각형에 쐐기가 존재 판단은 Prefix sum을 생각해볼 수 있다. 2차원 Prefix sum을 구성하며 사각형을 네 개의 변수 left, top, right, bottom으로 정의하여 O(1)로 내부에 쐐기가 있는지 없는지 판단할 수 있다.
이제 문제는 좌표값이 문제가 된다. 좌표 자체가 너무 크기 때문에 이를 해싱하기에는 메모리가 너무 모자란다. n이 최대 5000이기 때문에 서로 다른 x 또는 서로 다른 y의 값은 최대 5000개이다. 또 좌표값 자체에 의미가 있는 것이 아니라 작다, 같다, 크다 라는 비교기준만 있으면 되기 때문에 좌표압축을 통해 좌표값을 줄여준다. 이 과정은 O(n lg n)이므로 이 알고리즘의 시간 복잡도는 O(n^2)이 지배한다.
#include <vector>
#include <map>
#include <algorithm>
#include <vector>
using namespace std;
const int MAX_NM = 5000;
int solution(int n, vector<vector<int>> data) {
int answer = 0;
int i, j, xcnt = 0, ycnt = 0, l, t, r, b;
map<int, int> xm, ym;
vector<int> tmp;
for (i = 0; i<n; i++) tmp.push_back(data[i][0]);
sort(tmp.begin(), tmp.end());
for (i = 0; i<n; i++)
if (xm.find(tmp[i]) == xm.end()) {
xm[tmp[i]] = xcnt;
xcnt++;
}
tmp.clear(); tmp.resize(0);
for (i = 0; i<n; i++) tmp.push_back(data[i][1]);
sort(tmp.begin(), tmp.end());
for (i = 0; i<n; i++)
if (ym.find(tmp[i]) == ym.end()) {
ym[tmp[i]] = ycnt;
ycnt++;
}
vector<vector<int>> board(xcnt, vector<int>(ycnt, 0)), prefixSum(xcnt, vector<int>(ycnt, 0));
for (i = 0; i<n; i++)
board[xm[data[i][0]]][ym[data[i][1]]] = 1;
prefixSum[0][0] = board[0][0];
for (j = 1; j < ycnt; j++) prefixSum[0][j] = prefixSum[0][j-1]+board[0][j];
for (i = 1; i < xcnt; i++) {
prefixSum[i][0] = prefixSum[i - 1][0] + board[i][0];
for (j = 1; j < ycnt; j++) {
prefixSum[i][j] = board[i][j] + prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1];
}
}
for (i = 0; i<n; i++){
data[i][0] = xm[data[i][0]];
data[i][1] = ym[data[i][1]];
}
for (i = 0; i<n; i++) for (j = i + 1; j<n; j++) {
if (data[i][0] == data[j][0] || data[i][1] == data[j][1]) continue;
l = min(data[i][0], data[j][0]);
r = max(data[i][0], data[j][0]);
t = min(data[i][1], data[j][1]);
b = max(data[i][1], data[j][1]);
if (l + 1 <= r - 1 && t + 1 <= b - 1)
answer += (prefixSum[r - 1][b - 1] + prefixSum[l][t] - prefixSum[r - 1][t] - prefixSum[l][b - 1] == 0);
else answer++;
}
return answer;
}
6. 신비로운 유적 탐험
사실 이 문제와 똑같은 문제가 이전에 있었다.
http://poj.org/problem?id=2483
N이 최대 200이고 여러 테스트 케이스가 있다는 것을 제외하면 컨셉 자체는 똑같다.
[해설, 분류 - 재귀 호출, MCMF]
플로우 문제를 많이 풀어보긴 했지만, MCMF와 재귀가 만나는 경우는 처음인 것 같다. 내 머리로는 도저히 생각나지 않아 에디토리얼을 참고했다.
두 트리 g1,g2에 대해 각각 루트로 두고 비교할 대상을 a, b라고 하자. a의 자식들과 b의 자식들 중 각각 누구랑 같다가 두어야 매칭 결과가 최대가 되는지를 알아내는 것이 핵심이다. 이는 완전 탐색으로 충분히 가능하다. 재귀 호출을 하면서 a의 자식들과 b의 자식들을 O(n^2)으로 비교하여 무엇이 최대인지는 알 수 있다. 하지만 어떤 식으로 매칭을 시켜야 최대일지는 모르기 때문에 여기서 MCMF가 등장한다.
따라서 구조는 재귀 호출 함수 내부에서 MCMF를 사용해야 하며, 이분 그래프 상의 Supersource와 Supersink를 만들어서 돌린다. 이분 그래프이기 때문에 헝가리안 메소드를 사용하는 것도 가능하다.
※ 이분 그래프인 이유는 a의 자식이 a1, a2라고 할 때, 위에서 사용한 로직상 a1과 a2를 매칭으로 사용하지 않기 때문.
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int MAX_N = 100, MAX_V = 202;
int max_v(int a, int b) { return a > b ? a : b; }
struct Edge {
int v, f, c, ct, rn;
Edge() {}
Edge(int v, int f, int c, int ct, int rn)
: v(v), f(f), c(c), ct(ct), rn(rn) {}
int rc() { return c - f; }
void af(int amt, vector<vector<Edge>>& adj) {
f += amt;
adj[v][rn].f -= amt;
}
};
void addEdge(int u, int v, int c, int ct, vector<vector<Edge>>& adj) {
adj[u].push_back(Edge(v, 0, c, ct, (int)adj[v].size()));
adj[v].push_back(Edge(u, 0, 0, -ct, (int)adj[u].size() - 1));
}
int dist[MAX_V], bef[MAX_V];
vector<Edge*> path(MAX_V);
queue<int> q;
bool hasQ[MAX_V];
int mcmf(int& S, int& T, vector<vector<Edge>>& adj) {
int cost = 0, i;
while (1) {
memset(dist, 0x3F, sizeof dist);
memset(bef, -1, sizeof bef);
fill(path.begin(), path.end(), nullptr);
dist[S] = 0;
q.push(S);
while (!q.empty()) {
int u = q.front(); q.pop();
hasQ[u] = 0;
for (Edge& e : adj[u]) if (e.rc() > 0 && dist[e.v] > dist[u] + e.ct) {
dist[e.v] = dist[u] + e.ct;
bef[e.v] = u;
path[e.v] = &e;
if (!hasQ[e.v]) {
hasQ[e.v] = 1;
q.push(e.v);
}
}
}
if (bef[T] == -1) break;
for (i = T; i != S; i = bef[i]) {
cost += path[i]->ct;
path[i]->af(1, adj);
}
}
return -cost;
}
vector<vector<int>> adj1, adj2;
int f(int a, int b) {
int sz1 = (int)adj1[a].size(), sz2 = (int)adj2[b].size(), S, T, w, i, j;
S = sz1 + sz2;
T = S + 1;
vector<vector<Edge>> adj(T + 1);
for (i = 0; i<sz1; i++) {
addEdge(S, i, 1, 0, adj);
int& ac = adj1[a][i];
for (j = 0; j<sz2; j++) {
int& bc = adj2[b][j];
w = -f(ac, bc);
addEdge(i, sz1 + j, 1, w, adj);
}
}
for (j = 0; j<sz2; j++)
addEdge(sz1 + j, T, 1, 0, adj);
return mcmf(S, T, adj) + 1;
}
void build(int n, vector<vector<int>>& g, vector<vector<int>>& adj, vector<vector<int>>& tadj) {
int i, u, v;
queue<int> q;
vector<bool> vi(n, 0);
tadj.clear();
tadj.resize(n);
for (i = 0; i<n - 1; i++) {
u = g[i][0], v = g[i][1];
u--, v--;
tadj[u].push_back(v);
tadj[v].push_back(u);
}
vi[0] = 1;
q.push(0);
while (!q.empty()) {
u = q.front(), q.pop();
for (int& v : tadj[u]) if (!vi[v]) {
adj[u].push_back(v);
vi[v] = 1;
q.push(v);
}
}
}
int solution(int n1, vector<vector<int>> g1, int n2, vector<vector<int>> g2) {
int answer = 0, i, j, u, v;
adj1.clear();
adj2.clear();
adj1.resize(n1);
adj2.resize(n2);
vector<vector<int>> tadj;
build(n1, g1, adj1, tadj);
build(n2, g2, adj2, tadj);
return answer = f(0, 0);
}
