[백준]연구소(두번째풂)

https://www.acmicpc.net/problem/14502

14502번: 연구소

완전탐색dfs + bfs .

조합으로 하면 실행시간이 2~4배로 빨라 진다.

벽을 포함해서 계속 틀리게 나왔었음.... 문제를 잘 읽자 ..;

 

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
 
int N, M;
int map[8][8];
int isV[8][8];
int dr[] = { 0,0,-1,1 }, dc[] = { 1,-1,0,0 };
int ans = -1e9;
queue<pair<int, int> >q;
vector<pair<int, int> >v; //starting 
 
void bfs() {
    while(!q.empty()) {
        int r = q.front().first, c = q.front().second;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i], nc = c + dc[i];
            if (nr < 0 || nc < 0 || nr >= N || nc >= M || isV[nr][nc] == 1) continue;
            if (map[nr][nc] == 0) {
                q.push(make_pair(nr, nc));
                isV[nr][nc] = 1;
            }
        }
    }
}
 
void solve(int r, int len) {
    if (len == 3) {
        memset(isV, 0, sizeof(isV)); // 백업!!
        for (int i = 0; i < v.size(); i++) {
            int r = v[i].first, c = v[i].second;
            q.push(make_pair(r, c));
            isV[r][c] = 1;
        }
        bfs();
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) if (isV[i][j] == 0 &&  map[i][j]==0) cnt++;
        }
        if (cnt >= ans) ans = cnt;
        return;
    }
 
    for (int i = r; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (map[i][j] == 0) {
                map[i][j] = 1;
                solve(i, len + 1);
                map[i][j] = 0;
            }
        }
    }
}
 
int main()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) { 
            cin >> map[i][j]; 
            if (map[i][j] == 2) v.push_back(make_pair(i, j));
        }
    }
 
    solve(0, 0);
    printf("%d\n", ans);
    return 0;
}