(시간초과) 2146 다리만들기

#include <stdio.h>
#include <queue>
#include <utility>
#include <string.h>
 
using namespace std;
 
int arr[104][104] = { 0 };
int chk[104][104] = { 0 };
int chkMat[104][104] = { 0 };
int n, sum = 0;
 
void isLink(int a, int b) {
    queue<pair<int, int>> q;
    q.push(make_pair(a, b));
 
    int dx[4] = { 1,-1,0,0 };
    int dy[4] = { 0,0,1,-1 };
    while (!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;
        
        q.pop();
        chkMat[y][x] = -1;
 
        for (int i = 0; i < 4; i++) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            
            if (xx <= 0 || xx > n || yy <= 0 || yy > n)
                continue;
            if (chkMat[yy][xx] != 1)
                continue;
 
            q.push(make_pair(yy, xx));
        }
    }    
}
 
void scoreChk() {
    memcpy(chkMat, chk, sizeof(chk));
    int rst = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (chkMat[i][j] == 1) {
                isLink(i, j);
                rst++;
            }
        }
    }
    
    if (rst == 2)
        sum++;
}
 
void bridge(int cnt, int len) {
    if (cnt < len) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (chk[i][j] == 0) {
                    chk[i][j] = 1;
                    bridge(cnt + 1, len);
                    chk[i][j] = 0;
                }
            }
        }
    }
    else {
        if (sum == 0) {
            scoreChk();
        }            
    }
}
 
int main() {
    scanf("%d", &n);
 
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= n; j++) {
            scanf("%d", &arr[i][j]);
            chk[i][j] = arr[i][j];
        }
 
    for (int i = 1; i <= 3; i++) {
        bridge(0, i);        
        if (sum!=0) {
            printf("%d", i);
            break;
        }        
    }
}