14502 연구실

#include <stdio.h>
#include <queue>
#include <utility>
#include <string.h>
 
using namespace std;
 
int m[10][10] = { 0 };
int chk[10][10] = { 0 };
int row, col;
int maxRst = -1;
 
void bfsScore() {
    queue<pair<int, int>> q;
 
    int matChk[10][10] = { 0 };
    for (int i = 1; i <= row; i++) 
        for (int j = 1; j<= col; j++) {
            if (chk[i][j] == 2) {
                q.push(make_pair(i, j));                
            }
            else
                matChk[i][j] = chk[i][j];
        }
    
    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();
        matChk[y][x] = 1;
 
        for (int i = 0; i < 4; i++) {
            int xx = x + dx[i];
            int yy = y + dy[i];
 
            if (xx <= 0 || xx > col || yy <= 0 || yy > row)
                continue;
            if (matChk[yy][xx] != 0)
                continue;
 
            q.push(make_pair(yy, xx));
        }
    }
 
    int cnt = 0;
    for (int i = 1; i <= row; i++) 
        for (int j = 1; j <= col; j++) {
            if (matChk[i][j] == 0)
                cnt++;
        }
    
    if (maxRst < cnt) 
        maxRst = cnt;
}
 
void dfs(int count) {
    if (count == 3) {
        bfsScore();
        return;
    }
 
    for (int i = 1; i <= row; i++) 
        for (int j = 1; j <= col; j++) {
            if (chk[i][j] == 0) {
                chk[i][j] = 1;
                dfs(count + 1);
                chk[i][j] = 0;
            }
        }        
}
 
int main() {
    scanf("%d %d", &row, &col);
 
    for (int i = 1; i <= row; i++) 
        for (int j = 1; j <= col; j++) {
            scanf("%d", &m[i][j]);            
            chk[i][j] = m[i][j];
        }
    
    for (int i = 1; i <= row; i++) 
        for (int j = 1; j <= col; j++) {
            if (chk[i][j] == 0) {
                chk[i][j] = 1;
                dfs(1);                
                chk[i][j] = 0;
            }
        }    
 
    printf("%d", maxRst);
}

드디어 풀었다!!

DFS 를 활용하느 ㄴ방법을 잘 몰라서 헤멨는데, 꽤나 익숙해진 것 같다.

반드시 check 배열을 원상복귀 시켜놓으면서 DFS 를 돌려야 한다는걸 기억하자