[백준]꽃길

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

14620번: 꽃길

1.dfs를 이용한 완전탐색.

별다른건 없는 문제.

#include <iostream>
using namespace std;
 
int N, ans = 1e9;
int map[10][10];
int isV[10][10];
int dr[] = { 0,0,1,-1 }, dc[] = { 1,-1,0,0 };
 
bool check(int r, int c) {
    bool flag = true;
    for (int i = 0; i < 4; i++) {
        int nr = r + dr[i], nc = c + dc[i];
        if (isV[nr][nc] == 1) {
            return false;
        }
    }
    return flag;
}
 
void dfs(int r, int len) {
    if (len == 3) { 
        //꽃이 3개가 되면 핀 부분을 더해준다.
        int s = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (isV[i][j] == 1) s += map[i][j];
            }
        }
        if (ans >= s) ans = s;
        return; 
    }
 
    //외곽에서는 피지못하므로 범위를 잘 정해준다.
    for (int i = r; i < N - 1; i++) {
        for (int j = 1; j < N - 1; j++) {
            if (check(i, j) == true) {
                int nr, nc;
                isV[i][j] = 1;
                for (int k = 0; k < 4; k++) isV[i + dr[k]][j + dc[k]] = 1; 
                dfs(i, len + 1);
                isV[i][j] = 0;
                for (int k = 0; k < 4; k++) isV[i + dr[k]][j + dc[k]] = 0;
            }
        }
    }
}
 
int main()
{
    cin >> N;
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) cin >> map[i][j];
 
    dfs(1, 0);
    printf("%d\n", ans);
    return 0;
}