[백준/BOJ] 9525번 : 룩 배치하기 / 1760번 : N-Rook (이분 매칭)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 9525번 : '룩 배치하기', 1760번 : 'N-Rook' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제 난이도는 Solved.ac 기준 Platinum III에 해당하며, 문제를 풀이하기 위해 이분 매칭 알고리즘에 대한 이해가 필요합니다.

 

 

9525번 : 룩 배치하기

9525번: 룩 배치하기

 

빈칸과 폰의 위치를 나타내는 체스판의 입력이 주어졌을 때, 놓을 수 있는 최대 룩의 수를 구하는 문제입니다.

가운데 폰이 있는 경우 폰의 양쪽으로 룩을 배치할 수 있으므로 간단한 이분 매칭에 한 가지를 더 고려해야 하는 문제입니다.

 

 

 

먼저, 룩으로 한 행 또는 열을 선택하면 그 행이나 열에는 다른 룩이 올 수 없으므로, 이는 행과 열 사이의 이분 매칭으로 문제를 풀이할 수 있음을 의미합니다.

따라서 룩이 배치되었을 때 이동할 수 있는 행과 열을 번호로 매기고, 이들 사이에 이분 매칭을 수행해주면 됩니다.

예제를 그려서 간단하게 생각해보면, 우선 룩은 같은 행이나 열 내에서만 이동할 수 있으므로 행과 열로만 생각했을 때 놓을 수 있는 룩의 이동 경로를 그리고 각 룩의 번호로 칸을 채웁니다.

이제 이분 매칭을 수행시켜주면 위의 빨간 글씨로 표시한 부분의 원리에 의해 최대로 놓을 수 있는 룩의 수를 구할 수 있게 됩니다.

 

↓ 풀이 코드는 아래의 접은 글에 정리되어 있습니다.

#include <bits/stdc++.h>
using namespace std;
const int MSIZE = 105, MAX = 5005;

vector<int> Adj[MAX];
int Left[MAX], Right[MAX];
bool Visit[MAX];

bool DFS(int from) {
    Visit[from] = true;
    for(int i=0; i<Adj[from].size(); i++) {
        int to = Adj[from][i];
        if(Right[to] == -1 || (!Visit[Right[to]] && DFS(Right[to]))) {
            Left[from] = to, Right[to] = from;
            return true;
        }
    }
    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;
    char Map[MSIZE][MSIZE];
    for(int i=1; i<=N; i++) {
        cin.clear();
        for(int j=1; j<=N; j++) cin >> Map[i][j];
    }

    int rNum[MSIZE][MSIZE] = {}, cNum[MSIZE][MSIZE] = {}, cnt = 1;
    for(int i=1; i<=N; i++)
        for(int j=1; j<=N; j++)
            if(Map[i][j] == '.') {
                rNum[i][j] = cnt;
                if(j == N || Map[i][j+1] == 'X') cnt++;
            }
    int rCnt = cnt; cnt = 1;
    for(int i=1; i<=N; i++)
        for(int j=1; j<=N; j++)
            if(Map[j][i] == '.') {
                cNum[j][i] = cnt;
                if(j == N || Map[j+1][i] == 'X') cnt++;
            }

    for(int i=1; i<=N; i++)
        for(int j=1; j<=N; j++)
            if(Map[i][j] == '.') Adj[rNum[i][j]].push_back(cNum[i][j]);

    int match = 0;
    fill(Left, Left+MAX, -1), fill(Right, Right+MAX, -1);
    for(int i=1; i<=rCnt; i++) {
        fill(Visit, Visit+MAX, false);
        if(DFS(i)) match++;
    }

    cout << match;
}

 

맵을 입력받는 부분을 처리할 때에는, 입력에 개행 문자가 존재하므로 입력 버퍼를 비우는 등의 방식으로 역시나 주의해주도록 합니다.

나머지 부분의 구현은 일반적인 이분 매칭 풀이 코드와 동일합니다.

 

 

풀이 코드를 제출해보면 위와 같이 정답 처리를 받을 수 있습니다.

 

 

1760번 : N-Rook

1760번: N-Rook

 

위의 문제에서 약간 업그레이드 된 문제이나, Solved.ac 난이도는 Platinum III으로 동일합니다.

이 문제에서는 벽(입력으로는 2)에 해당하는 부분에 더해 말을 놓지 못하는 구덩이(입력으로는 1)이 존재합니다.

다만 이 부분은 아주 쉽게 처리할 수 있는데, 그저 입력이 1인 경우에는 행과 열 사이의 간선만 생성을 안 해주면 됩니다. (그러면 Rook을 놓을 위치로 선택할 수가 없기 때문)

 

↓ 풀이 코드는 아래의 접은 글에 정리되어 있습니다.

#include <bits/stdc++.h>
using namespace std;
const int MSIZE = 105, MAX = 5005;

vector<int> Adj[MAX];
int Left[MAX], Right[MAX];
bool Visit[MAX];

bool DFS(int from) {
    Visit[from] = true;
    for(int i=0; i<Adj[from].size(); i++) {
        int to = Adj[from][i];
        if(Right[to] == -1 || (!Visit[Right[to]] && DFS(Right[to]))) {
            Left[from] = to, Right[to] = from;
            return true;
        }
    }
    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, M; cin >> N >> M;
    int Map[MSIZE][MSIZE];
    for(int i=1; i<=N; i++)
        for(int j=1; j<=M; j++) cin >> Map[i][j];

    int rNum[MSIZE][MSIZE] = {}, cNum[MSIZE][MSIZE] = {}, cnt = 1;
    for(int i=1; i<=N; i++)
        for(int j=1; j<=M; j++) {
            if(Map[i][j] == 0) rNum[i][j] = cnt;
            if(Map[i][j] != 2 && (j == M || Map[i][j+1] == 2)) cnt++;
        }
    int rCnt = cnt; cnt = 1;
    for(int i=1; i<=M; i++)
        for(int j=1; j<=N; j++) {
            if(Map[j][i] == 0) cNum[j][i] = cnt;
            if(Map[j][i] != 2 && (j == N || Map[j+1][i] == 2)) cnt++;
        }

    for(int i=1; i<=N; i++)
        for(int j=1; j<=M; j++)
            if(Map[i][j] == 0) Adj[rNum[i][j]].push_back(cNum[i][j]);

    int match = 0;
    fill(Left, Left+MAX, -1), fill(Right, Right+MAX, -1);
    for(int i=1; i<=rCnt; i++) {
        fill(Visit, Visit+MAX, false);
        if(DFS(i)) match++;
    }

    cout << match;
}

 

풀이 코드 역시 거의 동일하나, Map의 입력을 정수로 받고 1과 2의 처리를 별개로 해주어야 한다는 점입니다.

그리고 다음에 벽이 있는지 검사할 때 현재 위치의 입력이 0뿐만 아니라 1인 경우에도 검사를 해주어야 합니다.

 

 

 

풀이 코드를 제출하면 위와 같이 정답 처리를 받을 수 있습니다.