[백준/BOJ C++][Diamond V] 12961번 : 체스판 2 (Network Flow)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 12961번 : 체스판 2 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제 난이도는 Solved.ac 기준 Diamond V에 해당하며, 문제를 풀이하기 위해 최대 유량 알고리즘(Network Flow)에 대한 이해가 필요합니다.

 

 

12961번 : 체스판 2

12961번: 체스판 2

 

입력으로 일부 칸에 말이 놓여져있는 체스판이 주어졌을 때 (검은색 타일에 L자 타일의 모서리가 오도록 배치한다고 할 때) L자 타일을 최대 몇 개 놓을 수 있는지 구하는 문제입니다.

 

 

 

솔직히 바로 이전 포스트에서 풀이한 '두부장수 장홍준 2' 문제를 풀면서 아이디어를 많이 얻었습니다.

L자 타일의 특성 상 두 흰색 칸의 좌표가 (홀수, 짝수), (짝수, 홀수) 관계에 있을 수밖에 없으므로, 홀수 행에서 흰색 칸을 찾아 유량을 보내고 거기서 다시 인접한 검은 칸으로, 마지막으로 짝수 행의 흰색 칸으로 보낸 뒤 Sink로 모아서 총 유량을 답으로 얻어낼 수 있습니다.

 

 

 

그래서 대략적인 input의 범위로 노드의 범위를 잡아주고, 모든 노드를 정점 분할하여 타일이 겹치지 않게 장치를 마련해줍니다.

(다른 분들의 풀이도 봤는데 저를 제외하고 전부 검은 칸만 분할해주셨던데, 메모리를 얼마나 아끼려고 했는지는 모르지만 개인적으로는 그냥 모든 노드를 분할하는 편이 편했습니다. 2*node-1, 2*node로 분할해주는 편이 넘버링 해주기에도 훨씬 편리함)

 

 

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 10005
#define INF 1000000000
using namespace std;

int R, C;
int in(int i, int j) { return ((i-1)*C+j)*2-1; }
int out(int i, int j) { return ((i-1)*C+j)*2; }

struct Edge {
    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];

void AddLine(int From, int To) {
    Edge* E = new Edge(From, To, 1);
    Edge* RevE = new Edge(To, From, 0);
    E->Rev = RevE, RevE->Rev = E;
    Line[From].push_back(E), Line[To].push_back(RevE);
}

int MaxFlow(int Sour, int Sink) {
    int FlowSum = 0;
    while(true) {
        vector<Edge*> Prev(MAX, nullptr);
        queue<int> Queue;
        Queue.push(Sour);

        while(!Queue.empty()) {
            int Curr = Queue.front(); Queue.pop();
            for(int i=0; i<Line[Curr].size(); i++) {
                int Next = Line[Curr][i]->To;
                if(Line[Curr][i]->Remain() > 0 && Prev[Next] == nullptr) {
                    Queue.push(Next);
                    Prev[Next] = Line[Curr][i];
                }
            }
        }
        if(Prev[Sink] == nullptr) break;

        int Amount = INF;
        for(int i=Sink; i!=Sour; i=Prev[i]->From)
            Amount = min(Amount, Prev[i]->Remain());
        for(int i=Sink; i!=Sour; i=Prev[i]->From)
            if(i != Sink && i != Sour+1) Prev[i]->AddFlow(Amount);
        FlowSum += Amount;
    }
    return FlowSum;
}

int main() {
    int Sour = 10001, Sink = 10002, Dir[2][4] = {{-1, 1, 0, 0}, {0, 0, -1, 1}};
    char Board[50][50];
    scanf("%d %d\n", &R, &C);
    for(int i=1; i<=R; i++) {
        for(int j=1; j<=C; j++) Board[i][j] = getchar();
        getchar();
    }
    for(int i=1; i<=R; i++)
        for(int j=1; j<=C; j++) {
            AddLine(in(i, j), out(i, j));
            if((i+j)%2 == 1 && i%2 == 1) AddLine(Sour, in(i, j));
            if((i+j)%2 == 1 && i%2 == 0) AddLine(out(i, j), Sink);
        }
    for(int i=1; i<=R; i++)
        for(int j=1; j<=C; j++) {
            if(Board[i][j] == 'X') continue;
            else if((i+j)%2 == 1 && i%2 == 1)
                for(int k=0; k<4; k++) {
                    int iNext = i+Dir[0][k], jNext = j+Dir[1][k];
                    if(!(iNext>=1 && iNext<=R && jNext>=1 && jNext<=C)) continue;
                    if(Board[iNext][jNext] == '.') AddLine(out(i, j), in(iNext, jNext));
                }
            else if((i+j)%2 == 1 && i%2 == 0)
                for(int k=0; k<4; k++) {
                    int iNext = i+Dir[0][k], jNext = j+Dir[1][k];
                    if(!(iNext>=1 && iNext<=R && jNext>=1 && jNext<=C)) continue;
                    if(Board[iNext][jNext] == '.') AddLine(out(iNext, jNext), in(i, j));
                }
        }
    printf("%d", MaxFlow(Sour, Sink));
}

 

그래서 위의 모식도를 바탕으로 풀이 코드를 작성하면 위와 같이 구현할 수 있습니다.

모든 조건문의 분기를 검은 칸((i+j)%2 == 0), 홀수 행의 하얀 칸((i+j)%2 == 1 && i%2 == 1), 짝수 행의 하얀 칸((i+j)%2 == 1 && i%2 == 0) 세 개의 그룹으로 나누어 처리하는 것을 확인할 수 있습니다.

 

 

 

 

+ 추가 내용

이걸 볼 사람이 있을지는 모르겠지만 혹시 답이 약간의 차이로 틀리게 나오시는 분들은 아래의 예외 케이스를 넣어서 확인해보시면 도움이 될 것입니다. (노드 연결이 중복되도록 연결한 경우에 해당)

 

3 4
X.XX
X..X
XX..

Ans : 1
Wrong Output : 2