#14620 꽃길 (C++)

링크 : www.acmicpc.net/problem/14620

14620번: 꽃길

 

문제풀이는 다음과 같았다.

 

조건 : 꽃을 심을 자리에 이전에 심어본 적이 없다면 (false 상태) 

(1) 꽃의 방향대로 자리값을 합산해주고 동시에 꽃을 심었다고 true로 표시해준다. 

(2) '기존 sum + 꽃의 방향대로 추가된 자릿값', 씨앗 갯수 -1로 DFS 진행

     -> 재귀를 통해 새롭게 꽃을 심을 자리를 찾으러감

(3) 다시 리셋(첫 번째로 꽃을 심을 자리를 변경)을 위해, 심었던 적이 있는 자리를 false로 되돌림

 

* 편의상 0이 아닌 1부터 배열을 잡았다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int arr[12][12], n = 0, mini = 3000, temp = 0, tempsum = 0;
bool check[12][12] = { false, };
int fh[4] = { 1,0,-1,0 }; // 시계방향 기준 꽃의 면적
int fw[4] = { 0,1,0,-1 };

int total(int a, int b) {
    tempsum = arr[a][b];
    check[a][b] = true;
    for (int i = 0; i < 4; i++) {
         tempsum += arr[a + fh[i]][b + fw[i]];
         check[a + fh[i]][b + fw[i]] = true;
    }
    return tempsum;
}

bool track(int a, int b) {
    if (a<2 || a>n - 1 || b<2 || b>n - 1) return false; // 2,2 미만 혹은 n-2,n-2를 초과하면 꽃을 못심음
    for (int i = 0; i < 4; i++) {
        if (check[a + fh[i]][b + fw[i]] == true) return false;
    }
    return true;
}

void untrack(int a, int b) {
    check[a][b] = false;
    for (int i = 0; i < 4; i++) {
        check[a + fh[i]][b + fw[i]] = false;
    }
    return;
}

void dfs(int sum, int num) {
    if (num == 0) {
        mini = min(mini, sum);
        return;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (track(i, j)) {
                temp = total(i, j); // (1)번 
                dfs(sum + temp, num - 1); // (2)번 // --num을 적지 않도록 주의
                untrack(i, j); // (3)번
            }
        }
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> arr[i][j];
        }
    }

    dfs(0, 3);

    cout << mini << "\n";

    return 0;
}

 

이 문제를 푸는데 오래 걸린 이유는, dfs(sum + temp, num -1)의 재귀 부분을 '--num'으로 잘못 표기했기 때문이었다. 

이렇게 해버리면 num += -1, 즉, num을 계속해서 마이너스 해버려서 충분한 횟수만큼 재귀를 진행할 수 없다.

 

참혹했던 뻘짓의 흔적