[백준] 14620번 꽃길 (C++)

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

 

 

이 문제는 N X N 격자가 주어졌을때 3개의 꽃잎을 놓았을 때 놓는 최소 비용을 구하는 문제이다.

 

그림을 자세히 보면 꽃잎을 놓는 정점에서 상하좌우로 1칸씩 퍼져서 꽃 모양을 완성하는 것을 알 수 있다.

 

이때 유의해야 할 점은 꽃끼리 겹치면 안되며 가장자리 칸같은 경우도 상, 하, 좌, 우 중 2개의 요소 이하를 벗어나기 때문에

포함할 수 없다.

 

최소 비용을 구하기위해서 그리디하게 가장 작은 격자 요소를 찾는다고 해도 이것이 최소 비용이 아닐 수 있기 때문에 다른 접근을 해봐야 한다.

 

N의 최대 크기가 10이기 때문에 100칸의 모든 경우의 수를 구하기엔 충분하다

O(100C3) 1억에 충분히 포함된다.

 

격자판의 모양이기 때문에 나는 dfs + 백트래킹을 사용하여 모든 경우의 수를 구하며 최솟값을 계속 update 해주었다.

 

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

struct nutrition {
    int p;
    int f;
    int s;
    int v;
    int cost;
};

int dx[] = {0 ,0, -1, 0, 1, 1, -1, -1, 1};
int dy[] = {0, -1, 0, 1, 0, -1, 1, -1, 1};
int N;
int graph[11][11];
bool visited[11][11];
int result = MAX;

bool cando(int x, int y) {
    for(int i = 0; i < 5; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if(nx < 0 || nx >= N || ny < 0 || ny >= N) return false;

        if(visited[nx][ny]) return false;
    }
    return true;
}

int extractcost(int x, int y) {
    int cost = 0;

    for(int i = 0; i < 5; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        cost += graph[nx][ny];
    }

    return cost;
}

void placeflower(int x, int y, int status) {
    if(status == 0) {
        for(int i = 0; i < 5; i++) { 
            int nx = x + dx[i];
            int ny = y + dy[i];

            visited[nx][ny] = true;
        }
    }
    else {
        for(int i = 0; i < 5; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            visited[nx][ny] = false;
        }
    }
}

void bt(int cnt, int totalcost) {
    if(cnt == 3) {
        result = min(result, totalcost);
        return;
    }

    for(int i = 1; i < N-1; i++) {
        for(int j = 1; j < N-1; j++) {
            if(cando(i, j)) {
                placeflower(i, j, 0);
                int tmpcost = extractcost(i, j);
                bt(cnt+1, totalcost + tmpcost);
                placeflower(i, j, 1);
            }
        }
    }
}

void solve() {
    bt(0, 0);

    cout << result;
}

void input() {
    cin >> N;

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            cin >> graph[i][j];
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}

 

코드를 하나씩 살펴보자

 

void bt(int cnt, int totalcost) {
    if(cnt == 3) {
        result = min(result, totalcost);
        return;
    }

    for(int i = 1; i < N-1; i++) {
        for(int j = 1; j < N-1; j++) {
            if(cando(i, j)) {
                placeflower(i, j, 0);
                int tmpcost = extractcost(i, j);
                bt(cnt+1, totalcost + tmpcost);
                placeflower(i, j, 1);
            }
        }
    }
}

 

먼저 bt함수는 모든 경우의 수를 구하는 재귀 형식의 함수이며 매개변수로 (꽃을 심었던 개수, 현재까지 꽃을 심은 비용)

으로 호출하였다.

cnt 즉 꽃을 심은 개수가 3일경우 totalcost와 정답을 비교하여 작은것으로 update 해주었다.

 

bool cando(int x, int y) {
    for(int i = 0; i < 5; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if(nx < 0 || nx >= N || ny < 0 || ny >= N) return false;

        if(visited[nx][ny]) return false;
    }
    return true;
}

 

두번째로 cando 함수이다. 이 함수는 bt함수에서 격자 요소를 탐색하면서 놓을 수 있는지 없는지 이 함수가 판별하는 것이다.

현재 좌표와 그 좌표에서 상하좌우를 탐색해서 놓을 수 있는 경우 true

하나라도 벗어나는 경우 false를 반환하여 판별하였다.

 

int extractcost(int x, int y) {
    int cost = 0;

    for(int i = 0; i < 5; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        cost += graph[nx][ny];
    }

    return cost;
}

 

extractcost 함수는 cando에서 놓을 수 있는경우 그 놓을 수 있는 위치의 합을 계산하여 값을 넘겨주는 함수이다.

 

void placeflower(int x, int y, int status) {
    if(status == 0) {
        for(int i = 0; i < 5; i++) { 
            int nx = x + dx[i];
            int ny = y + dy[i];

            visited[nx][ny] = true;
        }
    }
    else {
        for(int i = 0; i < 5; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            visited[nx][ny] = false;
        }
    }
}

 

placeflower 함수는 현재 놓았던 꽃을 다시 탐색하지 않기 위해서 방문체크를 해주는 함수이다.

따라서 놓을때는 방문체크를 해주고 다시 탐색할때는 방문체크를 해제하여 다시 탐색할 수 있게 하였다.