13200 light up

<백트래킹 + 이분매칭>으로 해결했다.

숫자가 1이상인 검은칸을 발견하면 vector<point>에 push_back 해주면서 map을 N-Rook을 풀 때 처럼 horizontal, vertical을 mapping해준다.

숫자가 0인 경우는 -1000으로 만들어 줘서 백트래킹 도중에 생기는 0인 칸과 헷갈리지 않도록 한다.

그 후 전구가 올 수 있는 곳에서 간선을 연결해주고 숫자가 1 이상인 검은칸에 대해서 백트래킹을 한다.

백트래킹은 상하좌우중 놓을 수 있는 곳이 있다면 그곳에 전구를 놓고 그 전구의 상하좌우의 숫자 1 이상인 검은 칸에 대해서 -=1 해준다.

당연히 전구를 놓는 곳 주변에 0인 칸이 있다면 불가능한 곳으로 인식한 후 다음 방향을 검색한다. dfs(x)의 x는 x번째 point를 뜻한다.

x==vector<point>.size()라면 true를 리턴한다. 전구를 놓을 때 당연히 horizontal, vertical을 체크한다. 그렇게 모두 배치한 다음 이분매칭을 진행한다.

이분매칭을 진행할 때 x와 pf[x]는 간선에 대한 정보일 뿐 좌표에 대한 정보가 아니므로 간선을 g에 추가할 때 좌표도 같이 추가해 주니 편했다.

ps. 코드 정말 더럽게 짜버렸다... 깔끔하게 만들어보고 싶다. 그리고 더 좋은 방법이 있을 것 같은데 생각이 나질 않는다.

#include <stdio.h>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
 
struct p {
    int x, y;
    p(int x, int y) : x(x), y(y) {}
    p operator+(const p &a) { return p(x + a.x, y + a.y); }
};
 
int t, n, map[7][7], h[7][7], v[7][7], dx[] = { 0,0,1,-1 }, dy[] = { 1,-1,0,0 }, res[7][7], pf[30];
bool c[30], hc[30], vc[30];
vector<pair<int, p>> g[30];
vector<p> sp;
 
bool check(int x, int y) {
    return x < 0 || y < 0 || x >= n || y >= n;
}
 
// x,y에 놓는게 불가능하다고 판단된 경우 되돌리기
void erase(int x, int y) {
    hc[h[x][y]] = vc[v[x][y]] = false;
    map[x][y] = -2;
    for (int j = 0; j < 4; j++) {
        int nx = x + dx[j], ny = y + dy[j];
        if (check(nx, ny) || map[nx][ny] < 0) continue;
        map[nx][ny]++;
    }
}
 
bool dfs(int x) {
    if (x == sp.size()) return true;
    p cur = sp[x];
    if (map[cur.x][cur.y] <= -1000 || map[cur.x][cur.y] == 0) return dfs(x + 1);
    else {
        for (int i = 0; i < 4; i++) {
            p nx = cur + p(dx[i], dy[i]);
            if (check(nx.x, nx.y) || map[nx.x][nx.y] != -2 || hc[h[nx.x][nx.y]] || vc[v[nx.x][nx.y]]) continue;
            bool f = true;
            for (int j = 0; j < 4 && f; j++) {
                p nnx = nx + p(dx[j], dy[j]);
                if (check(nnx.x, nnx.y)) continue;
                if (map[nnx.x][nnx.y] == 0 || map[nnx.x][nnx.y] == -1000) f = false;
            }
            if (f) {
                map[nx.x][nx.y] = -200;
                for (int j = 0; j < 4; j++) {
                    p nnx = nx + p(dx[j], dy[j]);
                    if (check(nnx.x, nnx.y) || map[nnx.x][nnx.y] <= 0) continue;
                    map[nnx.x][nnx.y]--;
                }
                hc[h[nx.x][nx.y]] = vc[v[nx.x][nx.y]] = true;
                // cur옆에 더 둘 수 있으면 x, 아니면 다음순서인 x+1
                if (dfs(x + (map[cur.x][cur.y] ? 0 : 1))) return true; 
                else erase(nx.x, nx.y);
            }
        }
    }
    return false;
}
 
int dfs2(int x) {
    if (x == -1) return 1;
    for (auto i : g[x]) {
        if (vc[i.first]|| c[i.first]) continue;
        bool f = false;
        for (int j = 0; j < 4; j++) {
            int nx = i.second.x + dx[j], ny = i.second.y + dy[j];
            if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
            if (map[nx][ny] == 0 || map[nx][ny] == -1000) {
                f = true;
                break;
            }
        }
        if (f) continue;
        c[i.first] = 1;
        if (dfs2(pf[i.first])) {
            pf[i.first] = x;
            return 1;
        }
    }
    return 0;
}
 
void init() {
    memset(h, -1, sizeof(h));
    memset(v, -1, sizeof(v));
    memset(hc, false, sizeof(hc));
    memset(vc, false, sizeof(vc));
    memset(res, 0, sizeof(res));
    memset(pf, -1, sizeof(pf));
    sp.clear();
    for (int i = 0; i < 30; i++) g[i].clear();
}
 
int main() {
    for (scanf("%d", &t); t--;) {
        init();
        scanf("%d", &n);
        int cnt = 0, cnt2 = 0, i, j;
        for (i = 0; i < n; i++) for (j = 0; j < n; j++) scanf("%d", &map[i][j]);
        // mapping
        for (i = 0; i < n; i++) {
            bool f1 = false, f2 = false;
            for (j = 0; j < n; j++) {
                if (map[i][j] == -2) h[i][j] = cnt, f1 = true;
                if (map[j][i] == -2) v[j][i] = cnt2, f2 = true;
                if (f1 && map[i][j] >= -1) cnt++, f1 = false;
                if (f2 && map[j][i] >= -1) cnt2++, f2 = false;
                if (map[i][j] > 0) sp.push_back({ i,j });
                else if (!map[i][j]) map[i][j] = -1000;
            }
            if (f1) cnt++, f1 = false;
            if (f2) cnt2++, f2 = false;
        }
        // edge 이어주기
        for (i = 0; i < n; i++) for (j = 0; j < n; j++) if (map[i][j] == -2) 
            g[h[i][j]].push_back({ v[i][j],{i,j} });
 
        dfs(0);
        for (int i = 0; i < 30; i++) {
            if (hc[i]) continue;
            memset(c, false, sizeof(c));
            dfs2(i);
        }
 
        for (i = 0; i < n; i++) for (j = 0; j < n; j++) 
            if (map[i][j] == -200) res[i][j] = 1;
        for (i = 0; i < 30; i++) {
            if (pf[i] == -1) continue;
            for (j = 0; j < g[pf[i]].size(); j++) if (g[pf[i]][j].first == i) {
                res[g[pf[i]][j].second.x][g[pf[i]][j].second.y] = 1;
                break;
            }
        }
        for (i = 0; i < n; i++, printf("\n")) for (j = 0; j < n; j++) 
            printf("%d ", res[i][j]);
    }
    return 0;
}