[그래프] TRAPCARD 함정 설치

1. 문제

 

타일이 주어지면 

 

'.'에 함정을 설치한다고 한다.

 

이때 함정은 상하좌우 4칸에 다른 함정이 없어야된다.

 

이때 최대 함정을 설치할 수 있는 갯수와

 

함정의 위치를 포함한 타일을 출력해야한다.

 

 

 

2. 암시적 그래프

 

타일을 상하좌우를 간선으로 가지는 암시적인 그래프로 표현할 수 있다.

 

이를 이용해 이분 그래프의 매칭 문제의 dfs코드를 조금 변형하면

 

최대한 많은 타일에 함정을 매칭할 수 있다.

 

이분 그래프로 생각하면 다음과 같다.

 

a그룹 = '#' 이 아닌 타일 전체

b그룹 = 상하좌우중간 으로 묶여진 타일들의 집합. 중간을 기준으로 구별할 수 있다.

 

 

3. 이분 그래프의 매칭 dfs

 

모든 타일을 조사하면서 '.' 인 타일에대해 dfs를 실행한다.

(a그룹을 하나씩 조사)

 

주위에 함정이 없어 함정을 설치할 수 있으면 설치하고

(해당 b그룹에서 함정이 매칭되지 않음)

 

설치할 수 없으면 재귀적으로 이미 설치된 함정의 위치를 옮기며 자리를 찾는다.

(b그룹에 매칭된 함정을 다른 b그룹에 매칭시킬 수 있는지 찾는다.) 

 

기존의 함정의 위치를 옮길때 중복되는 계산을 피하기위해 설치하고자하는 함정 위치를 기억한다.

 

 

결국 이 문제는 이분매칭으로 문제가 해결됨을 알 수 있다.

 

코드는 다음과 같다.

 

 

 

#include <iostream>
#include <algorithm>
#include <utility>
#include <cstring>
 
using namespace std;
 
const int dx[] = {0,0, -1, 1, 0};
const int dy[] = {0,-1, 0, 0, 1};
int H, W;
char gameBoard[24][24];
bool visited[24][24];
 
void showGameBoard()
{
    for(int i = 2; i < H+2; i++)
    {
        for(int j = 2; j < W+2; j++)
           cout<<gameBoard[i][j];
        cout<<"\n";
    }
}
bool dfs(int y, int x, bool isRecursion)
{
    if(visited[y][x]) return false;
 
    for(int i = 0; i < 5; i++)
    {
        int count = 0;
        bool isCanSet = true;
        int yy = y+dy[i];
        int xx = x+dx[i];
        if(gameBoard[yy][xx] == '.')
        {
            if(isRecursion) 
            {
                isRecursion = false;
                continue;
            }
            if(visited[yy][xx])continue;
            gameBoard[yy][xx] = '^';
            visited[yy][xx] = true;
            for(int j = 1; j < 5; j++)
            {
                int yyy = yy + dy[j];
                int xxx = xx + dx[j];
                if(gameBoard[yyy][xxx] == '#') continue;
 
                if(gameBoard[yyy][xxx] == '^')
                {
                    gameBoard[yyy][xxx] = '.';
                    if(dfs(yyy, xxx, true))
                        isCanSet = true;
                    else
                    {
                        isCanSet = false;
                        gameBoard[yyy][xxx] = '^';
                        break;
                    }
                }    
                count++;
            }
            if(isCanSet&&count > 0)
                return true;
            gameBoard[yy][xx] = '.';
        }
    }
    return false;
}
 
int solve()
{
    int ret = 0;
    for(int i = 2; i < H+2; i++)
        for(int j = 2; j < W+2; j++)
        {
            memset(visited, 0, sizeof visited);
            if(gameBoard[i][j] == '.')
                if(dfs(i, j, false)) ret++;
        }
    return ret;
}
 
 
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int C;
    cin>>C;
    while(C--)
    {
        cin>>H>>W;
        for(int i = 2; i < H+2; i++)
            for(int j = 2; j < W+2; j++)
                cin>>gameBoard[i][j];
        for(int i = 0; i < H+4; i++)
            gameBoard[i][0] = gameBoard[i][1] = gameBoard[i][W+2] = gameBoard[i][W+3] = '#';
        for(int i = 0; i < W+4; i++)
            gameBoard[0][i] = gameBoard[1][i] = gameBoard[H+2][i] = gameBoard[H+3][i] = '#';
 
        cout<<solve()<<"\n";
        showGameBoard();
    }
}

www.algospot.com/judge/problem/read/TRAPCARD

 

- 알고리즘 문제해결전략 1034p