티스토리 뷰
1. 문제 링크
https://www.acmicpc.net/problem/1420
1420번: 학교 가지마!
첫째 줄에 도시의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 100) 둘째 줄부터 N개의 줄에 도시의 모양이 주어진다. 비어있으면 점('.'), 벽은 '#', 도현이의 위치는 K, 학교의 위치는 H이다. K와 H는 하나만 주어진다.
www.acmicpc.net
2. 문제 개요
N*M크기의 모양이며, 1*1칸으로 나누어져 있다. 각 칸은 빈칸 또는 벽이다.
도현이는 현재 있는 칸과 상하좌우로 인접한 칸을 이동할 수 있다. 도현이를 학교에 가지 못하게 빈칸을 적절히 벽으로 바꾸려고 한다. 도현이가 학교에 가지 못하게 하기 위해서 빈칸을 벽으로 바꿔야 하는 횟수의 최솟값을 구하는 프로그램을 작성하시오.
3. 문제 힌트
그래프 1개를 독립된 2개로 쪼갤때 잘라야 하는 간선의 개수를 cut이라고 하고(용량이 1인 경우)
최소인 min cut은 max flow와 같다는 것을 사용.
4. 문제 풀기
이 문제는 정점을 막는다. 따라서 정점 1개를 들어오는 정점, 나가는 정점을 두어 관리해야 한다.
각 정점은 1번 막을 수 있으므로 정점 간의 간선 (in -> out)은 용량이 in에서 out으로만 1이어야 하고 양방향으로 연결시켜준다.
Node 간의 간선 연결은 용량을 INF를 줬다. 결국에 막는 것은 정점이니까 간선은 여러 번 접근해도 상관없으니깐 말이다. (1로 줘도 상관없으려나? 느낌상 INF를 줬는데..)
그리고 또 중요한 점은 100x100이다. 따라서 벽을 놓을 수 있는 정점은 9998개가 된다. (학교, 도현 제외)
그럼 배열을 거의 10000x10000을 선언하고 또 capacity, flow, 등 여러 개 선언해야 하므로 간선(edge) 구조체를 만들어서 리스트로 관리해야 한다. 다른 분들 코드를 보니 포인터 배열을 선언해서 간선을 관리하시던데 제가 작성한 코드에서는 포인터를 사용하지는 않았습니다. 그래서 코드가 직관적이지 않을 수 도 있습니다.(직관적이지 않다기보다는 이해하는데 오래 걸릴 수도..)
구조체의 다른 부분은 이해하기 쉽다고 생각하나 한 번에 이해가 안 되는 부분이 있다면 rev일 것입니다.
저도 구조체를 제가 직접 만든 것은 아니고 다른 문제를 풀다가 구조체로 관리하시는 분이 계시길래 구조체로 했습니다.
EDGE구조체를 담는 벡터는,
node [v] = (u, c, f, rev) 값을 갖습니다. v는 출발지 u는 도착지 c는 용량 f는 유량 rev는 역간선의 index입니다.
rev가 1이면, node [u] 벡터의 [1] 인덱스가 위 벡터의 역간선의 위치가 되는 것이죠.
대부분 코드를 안 보고 개념 및 알고리즘만 보고 문제를 푸시겠지만..
코드를 보시면 위점 유의해서 봐주시기 바랍니다 :)
아, 0개 놓을때도 -1로 출력하는 줄 알고 맞왜틀 했던.. 주의하세욧!!
5. 코드
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
char map[101][101];
int convertmap[101][101];
const int dx[] = { 1,-1,0,0 };
const int dy[] = { 0,0,1,-1 };
const int INF = 987654321;
int src, sink, cnt;
int n, m;
struct MaxFlow
{
MaxFlow() {}
MaxFlow(int node_size) { node.resize(node_size); }
struct EDGE {
EDGE() {}
EDGE(int uu, int cc, int ff, int rrev) :u(uu), c(cc), f(ff), rev(rrev) {}
int u, c, f, rev; //도착점, 용량, 유량, 역간선index
};
void add_edge_back(int v, int u, int c) {
node[v].emplace_back(u, c, 0, node[u].size());
node[u].emplace_back(v, 0, 0, node[v].size() - 1);
}
void get_MaxFlow() {
while (1)
{
vector<int> p, p_i;
p.resize(2 * cnt, -1);
p_i.resize(2 * cnt, -1);
queue<int> q;
q.push(src);
while (!q.empty()) {
int cur = q.front(); q.pop();
int len = node[cur].size();
for (int i = 0; i < len; ++i) {
int next = node[cur][i].u;
int nc = node[cur][i].c;
int nf = node[cur][i].f;
if (nc - nf > 0 && p[next] == -1) {
p[next] = cur;
p_i[next] = i;
q.push(next);
if (next == sink) break;
}
}
}
if (p[sink] == -1) break;
int minflow = INF;
for (int i = sink; i != src; i = p[i]) {
int p_v = p[i];
int p_e = p_i[i];
minflow = min(minflow, node[p_v][p_e].c - node[p_v][p_e].f);
}
for (int i = sink; i != src; i = p[i]) {
int p_v = p[i];
int p_e = p_i[i];
node[p_v][p_e].f += minflow;
node[node[p_v][p_e].u][node[p_v][p_e].rev].f -= minflow;
}
ans += minflow;
}
}
vector<vector<EDGE>> node;
int ans = 0;
};
int main()
{
scanf("%d %d", &n, &m);
for (int i = 0; i < n; ++i)
scanf("%s", &map[i]);
//received node number.
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
{
if (map[i][j] == 'K') {
src = cnt;
convertmap[i][j] = cnt++;
}
else if (map[i][j] == 'H') {
sink = cnt;
convertmap[i][j] = cnt++;
}
else if (map[i][j] == '.') {
convertmap[i][j] = cnt++;
}
else {
convertmap[i][j] = -1;
}
}
src += cnt;
//allocate MaxFlow adj list.
MaxFlow mf(cnt * 2);
//separate node.
//inner node.
for (int i = 0; i < cnt; ++i)
mf.add_edge_back(i, cnt + i, 1);
//inter node.
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
if (convertmap[i][j] != -1) {
int cy = i, cx = j, cnode = convertmap[i][j];
for (int dir = 0; dir < 4; ++dir) {
int nx = cx + dx[dir];
int ny = cy + dy[dir];
//boundary check.
if (nx < 0 || ny < 0 || nx >= m || ny >= n || convertmap[ny][nx] == -1)
continue;
int nnode = convertmap[ny][nx];
mf.add_edge_back(cnode + cnt, nnode, INF);
}
}
mf.get_MaxFlow();
bool err = false;
for (int i = 0; i < mf.node[src].size(); ++i)
if (mf.node[src][i].u == sink)
err = true;
if (err)
printf("-1");
else
printf("%d", mf.ans);
return 0;
}
6. 결과 사진
지적, 댓글 언제나 환영입니다~