1. dfs를 사용해서 depth 3 까지 구합니다. 2. 헷갈리는 부분이 씨앗음 심고 나서, for 문이 그 뒤로만 들어가도록 하고 싶은데, 그렇게는 못하고, 그냥 2중 포문으로 중복이 포함되도록 풀이 했습니다. 이렇게 해도 통과는 되는데, 3. 어떻게 하면 중복되지 않고, for 문 i,j 가 순서대로 검사하도록 할 수 있을까요? 포문 시작을 i, j 로 넣으면 시작은 잘 되는데 다시 아이가 변경될때 제이가 0으로 오지않고, 다른 숫자로 오게 됩니다. 그럼 i 는 그대로 넣고 j를 해볼까요? |
/* 14:52 시작합니다. 서로 달ㄴ 3개 씨앗 꽃이 피게하면서 가장 싼 가격에 화단을 대여하려고 합니다. 꽃하나당 5평의 땅을 대여해야 합니다. 꽃을 심기 위해 필요한 최소 비용을 구해주세요. 십자가 문양이 3개 들어가도록 합니다. 비지트를 만들어서 다른 곳에 둘 수 없도록 합니다. dfs 로 풀어야 하겠습니다. 심을 수 있는지 없는지 체크를 하면서 심고 넘어가고 depth 는 3으로 둡니다. */ #include <iostream> #include <algorithm> using namespace std; #define SIZE 12 // 12 int x, y, nx, ny; int map[SIZE][SIZE]; int visit[SIZE][SIZE]; int sum; int N; int minVal = 2123456789; void problemIn() { cin >> N; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { cin >> map[i][j]; } } } // 맵 안에 들어오는지, 다른 꽃은 없는지 체크해서 괜찮으면 1 출력, 안 괜찮으면 0 출력 int check(int x, int y) { if (x + 1 < N && x - 1 >= 0 && y - 1 >= 0 && y + 1 < N) { if (visit[x][y] == 0 && visit[x+1][y] == 0 && visit[x-1][y] == 0 && visit[x][y+1] == 0 && visit[x][y-1] == 0) { return 1; } } return 0; } void dfs(int depth, int x, int y, int sum) { if (depth == 3) { minVal = min(minVal, sum); return; }
for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (check(i, j)) { visit[i][j] = visit[i + 1][j] = visit[i - 1][j] = visit[i][j + 1] = visit[i][j - 1] = 1; sum = sum + map[i][j] + map[i + 1][j] + map[i - 1][j] + map[i][j + 1] + map[i][j - 1]; dfs(depth + 1, i, j, sum); visit[i][j] = visit[i + 1][j] = visit[i - 1][j] = visit[i][j + 1] = visit[i][j - 1] = 0; sum = sum - map[i][j] - map[i + 1][j] - map[i - 1][j] - map[i][j + 1] - map[i][j - 1]; } } } } void solve() { dfs(0, 0, 0, 0); } int main() { problemIn(); solve(); cout << minVal << endl; return 0; } |