백준18447 Angle Beats

작성일 | In

문제 링크

  • http://icpc.me/18447

사용 알고리즘

  • 일반 그래프 매칭

풀이

*에는 항상 L 형태의 블록을 배치해야 하고, +에는 I와 L 중 원하는 것을 배치할 수 있습니다. *와 + 모두 인접한 네 칸 중 정확히 두 칸과 매칭되어야 합니다.

.이 아닌 격자의 각 칸 $(i, j)$마다 2개의 정점 $(i, j, 0), (i, j, 1)$을 만들 것입니다.
$A(i,j)=\ast$ 이면 $(i,j)$는 위/아래 중 하나, 그리고 왼쪽/오른쪽 중 하나와 연결되어야 합니다. $(i,j,0)$을 $(i-1,j,0), (i+1,j,0)$과 연결하고, $(i,j,1)$은 $(i,j-1,0), (i,j+1,0)$과 연결합시다.
$A(i,j)=+$ 이면 $(i,j)$는 인접한 네 칸 중 아무거나 두 개를 선택해서 연결하면 됩니다. $(i,j,0)$과 $(i,j,1)$ 모두 인접한 네 칸의 격자 칸과 연결합시다.

격자를 블록으로 채우기 위해서는, .이 아닌 칸이 모두 두 개의 정점과 매칭되어야 하고, 이는 .이 아닌 칸마다 간선이 2개씩 연결되는 최대 매칭을 찾으면 됩니다. 이런 문제는 NERC’18 Bimatching이라는 문제로 잘 알려져 있고, 일반 그래프 매칭으로 해결하는 방법이 koosaga님 블로그에 잘 설명되어 있습니다.
구현은 아래 코드의 15~36번 줄을 참고하시면 됩니다.

아무튼 매칭을 구했다면, 이제 출력을 해야 합니다. 인접한 블록을 서로 다른 알파벳으로 출력해야 합니다.
많이 귀찮을 것 같지만 격자 그래프가 평면 그래프라는 점을 이용하면 어렵지 않습니다. 평면 그래프에는 항상 차수가 5 이하인 정점이 존재하기 때문에, 차수가 최소인 정점을 찾아서 하나씩 제거하는 방식으로 정점을 색칠할 수 있습니다.
자세한 방법은 아래 코드의 48번째 줄 이후를 확인하시면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
constexpr int di[] = {1, -1, 0, 0};
constexpr int dj[] = {0, 0, 1, -1};

int N, M, K, R[111][111];
char A[111][111];
inline int ID(int i, int j){ return (i-1)*M+j-1; }
inline int ID(int i, int j, int flag){ return ID(i,j) * 2 + flag + 1; }
vector<int> G[10101]; int C[10101], D[10101];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M;
    for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) cin >> A[i][j];

    Graph Solver(N*M*2+1);
    for(int i=1; i<=N; i++){
        for(int j=1; j<=M; j++){
            if(A[i][j] != '.'){ Solver.add_edge(ID(i,j,0), ID(i,j,1)); continue; }
            for(int k=0; k<4; k++){
                int ii = i + di[k], jj = j + dj[k];
                if(A[ii][jj] == '+') Solver.add_edge(ID(i,j,0), ID(ii,jj,0)), Solver.add_edge(ID(i,j,0), ID(ii,jj,1));
                if(A[ii][jj] == '*') Solver.add_edge(ID(i,j,0), ID(ii,jj,k/2));
            }
        }
    }
    Solver.run();

    const auto match = Solver.match;
    for(int i=1; i<=N; i++){
        for(int j=1; j<=M; j++){
            if(A[i][j] == '.') continue;
            if(match[ID(i,j,0)] == ID(i,j,1) || !match[ID(i,j,0)] || !match[ID(i,j,1)]) continue;
            int u = (match[ID(i,j,0)] - 1) / 2, v = (match[ID(i,j,1)] - 1) / 2;
            R[i][j] = R[u/M+1][u%M+1] = R[v/M+1][v%M+1] = ++K;
        }
    }

    for(int i=1; i<=N; i++){
        for(int j=1; j<=M; j++){
            for(int k=0; k<4; k++){
                int ii = i + di[k], jj = j + dj[k], u = R[i][j], v = R[ii][jj];
                if(u && v && u != v) G[u].push_back(v), G[v].push_back(u);
            }
        }
    }
    for(int i=1; i<=K; i++) sort(G[i].begin(), G[i].end()), G[i].erase(unique(G[i].begin(), G[i].end()), G[i].end()), D[i] = G[i].size();

    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> Q;
    for(int i=1; i<=K; i++) Q.emplace(D[i], i);
    while(!Q.empty()){
        auto [d,v] = Q.top(); Q.pop();
        if(C[v]) continue;
        int chk[7] = {0};
        for(auto i : G[v]) chk[C[i]] = 1;
        for(int i=1; i<=6; i++) if(!chk[i]) { C[v] = i; break; }
        for(auto i : G[v]) if(!C[i]) Q.emplace(--D[i], i);
    }

    for(int i=1; i<=N; i++){
        for(int j=1; j<=M; j++){
            if(R[i][j] == 0) cout << A[i][j];
            else cout << char(C[R[i][j]]-1+'a');
        }
        cout << "\n";
    }
}