Crocus

[1420번] 학교 가지마!

문제 출처 :

https://www.acmicpc.net/problem/1420

알고리즘 분석 :

문제 해결에 필요한 사항

1. 네트워크 플로우 :: http://www.crocus.co.kr/741

2. 최대 유량

3. 최소 컷(Min Cut)

아직 네트워크 플로우의 문제들에 대해 친밀도가 많이 부족하여 이 문제를 푸는데 상당한 시간이 걸린 것 같다.

첫 제출에서 WA를 받고 계속된 제출이후 마지막에 알게 된 것이 네트워크 플로우의 가장 기본 원칙인 역방향 간선을 추가하지 않아서 계속 틀리고 있었던 것이다.

이 문제는 위의 사진 처럼 기본적인 연결은 다음과 같다.

하지만 위의 화살표 반대 방향으로 화살표를 모두 그려주어야 한다.(용량은 0으로 설정하면 된다.)

그래야 네트워크 플로우 기본 속성(원칙)에 맞아 떨어지게 된다.

우선 해결 방법으로는 노드 방문여부이니 visit로 해결해 볼 수도 있지만, 이번에는 하나의 노드를 두개의 노드로 쪼개어 활용하였다.

하나의 노드가 쪼개지면 사이에 간선이 생기는데 그 용량을 1로 두고 거기에 유량이 흐르게 되면 노드를 방문했는 것과 같게 된다.

그리고 다른 간선은 모두 INF로 용량을 두어 최대 유량을 구하면 된다.

왜 최대 유량을 구하면 되냐면, 결국 학교를 못가게 벽을 설치하기 위해 최소 몇개의 벽을 설치해야 하나? 에서

최소 컷이라는 개념이 생각나게되고, 최소 컷은 최대 유량과 같다는 것을 이용하여 풀 수 있기 때문이다.

소스 코드 :

#include <iostream>

#include <cstdio>

#include <vector>

#include <memory.h>

#include <queue>

#include <cmath>

#include <map>

#define MAX_N 20002

#define INF 987654321

using namespace std;

char arr[101][101];

vector<int> adj[MAX_N];

map<pair<int, int>, int> cMap;

map<pair<int, int>, int> fMap;

int main()

{

    int n, m;

    int S = -1, T = -1, cnt = 0;

    int sx, sy, tx, ty;

    scanf("%d %d", &n, &m);

    getchar();

    for (int i = 0; i < n; i++)

{

        for (int j = 0; j < m; j++)

{

            scanf("%c", &arr[i][j]);

            if (arr[i][j] == 'K')

{

                S = cnt + 1;

                sx = j;

                sy = i;

}

            else if (arr[i][j] == 'H')

{

                T = cnt;

                tx = j;

                ty = i;

}

            cnt += 2;

}

        getchar();

}

    // 예외처리, n,m이 1일때, H또는 K가 없을 때, H와 K가 인접해 있을 때

    if ((n == 1 && m == 1) || S == -1 || T == -1 || abs(sx - tx) + abs(sy - ty) == 1)

{

        printf("-1\n");

        return 0;

}

    // 정점을 2개로 쪼갠다.

    for (int i = 0; i < n * m; i++)

{

        // in :: 0, 2, 4 ... out :: 1, 3, 5 ...

        cMap[{2 * i, 2 * i + 1}] = 1;

        adj[2 * i].push_back(2 * i + 1); 

        cMap[{2 * i + 1, 2 * i}] = 0;

        adj[2 * i + 1].push_back(2 * i);

}

    // 간선 연결 작업(왼쪽 위부터 오른쪽 아래로 작업)

    // 정방향 간선 및 역방향 간선 추가

    int from = 0;

    for (int i = 0; i < n; i++)

        for (int j = 0; j < m; j++)

{

            if (j + 1 < m && arr[i][j] != '#' && arr[i][j + 1] != '#')

{

                int to = from + 2;

                cMap[{from + 1, to}] = INF;

                cMap[{to, from + 1}] = 0;

                cMap[{to + 1, from}] = INF;

                cMap[{from, to + 1}] = 0;

                adj[from + 1].push_back(to);

                adj[to].push_back(from + 1);

                adj[to + 1].push_back(from);

                adj[from].push_back(to + 1);

}

            if (i + 1 < n && arr[i][j] != '#' && arr[i + 1][j] != '#')

{

                int to = 2 * m + from;

                cMap[{from + 1, to}] = INF;

                cMap[{to, from + 1}] = 0;

                cMap[{to + 1, from}] = INF;

                cMap[{from, to + 1}] = 0;

                adj[from + 1].push_back(to);

                adj[to].push_back(from + 1);

                adj[to + 1].push_back(from);

                adj[from].push_back(to + 1);

}

            from += 2;

}

    int totalFlow = 0;

// 에드몬드 카프 알고리즘

    while (1)

{

        int prev[MAX_N];

        memset(prev, -1, sizeof(prev));

        queue<int> q;

        q.push(S);

        while (!q.empty())

{

            int cur = q.front();

            q.pop();

            for (int i = 0; i < adj[cur].size(); i++)

{

                int next = adj[cur][i];

                if (prev[next] != -1)

                    continue;

                if (cMap[{cur, next}] - fMap[{cur, next}] > 0)

{

                    q.push(next);

                    prev[next] = cur;

                    if (next == T)

                        break;

}

}

}

        if (prev[T] == -1)

            break;

        for (int i = T; i != S; i = prev[i])

{

            fMap[{prev[i], i}] += 1;

            fMap[{i, prev[i]}] -= 1;

}

        totalFlow += 1;

}

    printf("%d\n", totalFlow);

    return 0;

}

//                                                       This source code Copyright belongs to Crocus

//                                                        If you want to see more? click here >>