건물세우기(BASIC2)(DFS)

문제 설명

---

(주)정올에서는 여러 개의 빌딩을 새로 지을 계획이다. 그래서 빌딩을 세울 장소를 선정하였다. 그리고 각 빌딩을 각 장소에 세울 경우에 드는 비용을 추정하였다. 예를 들어서 아래의 표를 보자

         1 2 3
       A 4 7 3
       B 2 6 1
       C 3 9 4

A, B, C 는 건물을 나타내고, 1, 2, 3은 장소를 나타낸다. 예를 들어서 건물 B를 장소 1에 세우면 비용이 2가 들고, 장소 2에 세우면 비용이 6, 장소 3에 세우면 비용이 1만큼 든다. 물론 한 장소에는 한 건물밖에 세울 수 없다. 만일 A를 장소 2에, B를 장소 3에, C를 1에 세우면 전체 비용이 7+1+3 = 11이 필요하다. 그런데 A를 3, B를 1, C를 2에 세우면 3+2+9 = 14 가 필요하다.

각 빌딩을 어느 장소에 세우면 비용의 합이 최소가 되는지 구하는 프로그램을 작성하시오.

입력 설명

---

입력 파일의 첫 줄은 빌딩의 개수 n(1≤n≤10)이 들어있다.
그 다음 n 줄에는 각 건물을 각 장소에 세울 경우에 드는 비용이 입력된다. 물론 각 줄 에는 n개의 수가 입력된다.
비용을 나타내는 수의 범위는 1이상 100미만이다.

출력 설명

---

첫 줄에는 최소비용을 출력한다.

입력 예시

---

4
11 12 18 40
14 15 13 22
11 17 19 23
17 14 20 28

출력 예시

---

61

#include <stdio.h>
#define MAXN (10)
int N;//빌딩개수(장소개수)
int A[MAXN+10][MAXN+10];//[빌딩][장소]=비용
 
int sol;
int used[MAXN+10];//순열위해..
 
void DFS(int n, int sum){//건물인덱스, 누적비용
    if (sol <= sum) return;//가지치기, 중간값이 이전 답보다 좋지 않은 경우
    if (n > N){//종료 조건(모든 건물 다 지음)
        sol = sum;//새로운 비용이 이전 보다 좋은 경우
        return;
    }
     
    for (int i=1; i<=N; i++){//장소 인덱스
        if (used[i]) continue;//i번 장소 사용 중 skip
        used[i]=1;//사용표시
        DFS(n+1, sum+A[n][i]);
        used[i]=0;//표시제거
    }
}
 
int Solve(void){
    sol = 100 * MAXN;//최솟값 구하므로 최댓값으로 초기화
    DFS(1, 0);//건물인덱스, 누적비용
    return sol;
}
 
void InputData(void){
    scanf("%d", &N);
    for (int i=1; i<=N; i++){//빌딩 인덱스
        for (int j=1; j<=N; j++){//장소 인덱스
            scanf("%d", &A[i][j]);
        }
    }
}
 
int main(void){
    InputData();
    int ans = Solve();
    printf("%d\n", ans);
    return 0;
}