[정올] 1681번: 해밀턴 순환회로

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=954 

JUNGOL

 

문제 이해

가능한 경로들 중에 최적의 경로를 찾는 것이기 때문에 (최소 비용 구하기) DFS를 돌리면 되는 문제이다.

 

Depth 는 총 배달해야 하는 장소의 개수 (12)이다. 사실 12개의 초이스들을 12번 선택해야 하기 때문에 상당히 수가 크지만, (12!) 이미 방문한 곳은 다시 방문하지 않기 때문에 충분히 작아질 수 있다. 또한, 마지막 가지치기를 하면 생각보다 가지가 많이 뻗지 않을 수있다. 

 

기본적으로 DFS를 돌릴 때는 depth가 12가 넘어가지 않는 정도면 해낼 수 있다고 생각하면 된다.

 

회사(1)에서 출발해서, 가능한 경로들을 하나하나 선택하며 모든 곳을 방문할 때까지 돈다. 이미 방문한 곳이면 패스하면 된다. 이미 방문했는지 여부는 visited 배열을 참고한다

 

만약 도착지에 도착했다면, 여기서 다시 회사로 돌아갈 수 있는지를 확인해야하며, 회사로 돌아갈 수 있다면 지금까지의 비용과 최소 비용을 비교해서 갱신한다. 

 

각 DFS에서 만약 현재까지의 비용이 전에 구한 최소 비용보다 크면 그냥 거기서 끝내면 된다. (그른 루트이므로)

 

작성 코드

#include <stdio.h>

int N;
int graph[12 + 3][12 + 3];
int visited[12 + 3];
int min_cost = 0x7fffffff;

void dfs(int node, int cnt, int cost) {

    // 3. 가지치기
    if (cost > min_cost) return;
    // 2. 종료 조건
    if (cnt >= N) {
        // 다 돌았다.
        if (graph[node][1] == 0) return; // 시작점으로 못돌아감
        cost += graph[node][1];// 시작점으로 돌아간다.
        if (cost < min_cost) min_cost = cost;
        return; // 집으로 돌아감
    }

    // 1. 재귀함수 설계
    for (int i = 1; i <= N; i++) {
        visited[node] = 1;
        if (graph[node][i] != 0 && visited[i] == 0) {
            // 연결되어 있고, 방문한 적 없다면
            dfs(i, cnt + 1, cost + graph[node][i]); // 다음 노드 선택
        }
        visited[node] = 0;
    }
}

int main(void) {

    int ans;
    // 입력 받기
    scanf("%d", &N);
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            scanf("%d", &graph[i][j]);
        }
    }

    // dfs
    dfs(1, 1, 0);
    ans = min_cost;

    //출력
    printf("%d", ans);

    return 0;
}