[C++] 1420번 학교 가지마! - 최대 유량, 최대 유량 최소 컷 정리

1. 문제

• N*M 크기의 도시는 빈칸 또는 벽이다. 도현이와 학교는 빈칸에 있고 도현이는 상하좌우로 인접한 칸으로 이동해 학교에 가려고 한다. 이때, 벽이 있는 칸으로는 이동할 수 없고, 도시를 벗어날 수 없을 때 도현이가 학교에 가지 못하게 빈칸을 벽으로 바꾸려고 한다. 도현이와 학교가 있는 곳은 벽으로 바꿀 수 없을 때 바꿔야 하는 횟수의 최솟값을 구하시오.

<입력>

• -1-   도시의 세로 크기 N, 가로 크기 M \(M(1 \leq N, M \leq 100)\)
• M개의 줄   도시의 모양이 주어진다. 빈칸: '.', 벽: '#', 도현이의 위치: 'K', 학교의 위치: 'H'. K와 H는 하나만 주어진다.

<출력>

• 바뀌는 벽의 최솟값을 출력하라. 만약 벽을 세워도 막을 수 없다면 -1을 출력하라.

2. 재정의

• 바뀌는 벽의 최솟값을 출력하라. 만약 벽을 세워도 막을 수 없다면 -1을 출력하라.

3. 해결 방법

• 아무리 고민해도 풀리지 않아서.. 결국 타인의 블로그를 참고해서 코드를 작성하였다.
• 동적배열을 사용하지 않고 작성한 깔끔한 코드가 있어서 아래에 링크하였다.

 

<코드>

#include <iostream>
#include <string.h>
#include <vector>
#include <queue>

using namespace std;

const int INF = 987654321;
const int MAX_N = 10001;
const int MAX_EDGE = 25000;
const int MAX_LENGTH = 101;
const int MAX_WIDTH = 101;


//도시의 세로 크기 N, 도시의 가로 크기 M
int N, M;
//유량 알고리즘 sour, sink, 최대 유량
int sour, sink, total_flow;
//도시
char Map[MAX_LENGTH][MAX_WIDTH];

bool impossible;

struct Edge {
    //from에서 to로 가는 간선의 용량 Capacity과 유량 Flow
    int from, to, Capacity, Flow;
    //역방향 간선
    Edge* Rev;
    
    Edge(int U, int V, int C) : from(U), to(V), Capacity(C), Flow(0) {}
    //더 흘러 보낼 수 있는 유량
    int Remain() { return Capacity - Flow; }
    //유량 증가시키기
    void AddFlow(int amount) {
        Flow += amount;
        Rev->Flow -= amount;
    }
};
//간선
vector<Edge*> Line[MAX_EDGE];

//간선 생성하기
void AddLine(int from, int to, int Capacity) {
    Edge* E = new Edge(from, to, Capacity);
    Edge* RevE = new Edge(to, from, 0);
    E->Rev = RevE, RevE->Rev = E;
    Line[from].push_back(E), Line[to].push_back(RevE);
}

void input() {
    cin >> N >> M;
    
    //정점 분리
    for(int i=1; i<=M*N*2; i+=2)
        AddLine(i, i+1, 1);
    
    for(int i=1; i<=N; i++) {
        for(int j=1; j<=M; j++) {
            cin >> Map[i][j];
            //S와 E가 붙어있으므로 벽을 설치해도 막을 수 없다. 따라서 -1출력 후 종료
            if(Map[i][j] != '.' && Map[i][j] != '#' && ((j>1 && Map[i][j-1] != '.' && Map[i][j-1] != '#') || (i>1 && Map[i-1][j] != '.' && Map[i-1][j] != '#'))) {
                impossible = true;
                return;
            }
            //정점 분리
            else if(Map[i][j] == 'K')
                sour = ((i-1)*M+j)*2;
            else if(Map[i][j] == 'H')
                sink = ((i-1)*M+j)*2-1;
        }
    }
    
    //최대 유량 알고리즘을 적용시킬 그래프 만들기
    for(int i=1; i<=N; i++) {
        for(int j=1; j<=M; j++) {
            //탐색한 점이 벽일 경우 pass
            if(Map[i][j] == '#')
                continue;
            if(j+1<=M && Map[i][j+1] != '#') {
                AddLine(((i-1)*M+j)*2, ((i-1)*M+j+1)*2-1, 1);
                AddLine(((i-1)*M+j+1)*2, ((i-1)*M+j)*2-1, 1);
            }
            if(i+1<=N && Map[i+1][j] != '#') {
                AddLine(((i-1)*M+j)*2, (i*M+j)*2-1, 1);
                AddLine((i*M+j)*2, ((i-1)*M+j)*2-1, 1);
            }
        }
    }
}

//최대 유량 알고리즘
void MaxFlow() {
    while(1) {
        //BFS
        vector<Edge*> Prev(MAX_EDGE, nullptr);
        
        queue<int> q;
        q.push(sour);
        
        while(!q.empty() && Prev[sink] == nullptr) {
            int here = q.front(); q.pop();
            
            for(int i=0; i<Line[here].size(); i++) {
                int Next = Line[here][i]->to;
                
                if(Line[here][i]->Remain() > 0 && Prev[Next] == nullptr) {
                    q.push(Next);
                    Prev[Next] = Line[here][i];
                }
            }
        }
        
        if(Prev[sink] == nullptr)
            break;
        
        for(int i=sink; i!=sour; i=Prev[i]->from)
            if(i!=sink)
                Prev[i]->AddFlow(1);
        
        total_flow++;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    input();
    
    MaxFlow();
    
    if(impossible)
        cout << -1;
    else
        cout << total_flow;
    
    return 0;
}

 

<참고한 코드(풀어야 볼 수 있습니다.)>

https://www.acmicpc.net/source/14173638

로그인

 

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.