연구활동 가는 길

DFS의 전형적인 문제형식이다. 

 

연결리스트, 인접행렬 두가지방식으로 풀수있는데 코드는 본문 맨아래 서술해놨다.

 

우선 배열로 목적지와 값을저장한후 가장 작은값이 나올때마다 최종값(lv)을 변경하는방법인 연결리스트는 아래와같다.

1 => 2  (0+47) , 2=>4 (47+57) , 4=> 6 (104+27) , 6=>7 (131+40)   목적지 도달 => lv = 171

인접 행렬의 경우 모든 목적지를 탐색한다. 시간의 소모가 크지만 구현하기 쉽다.

배열의 크기는 최대 10x10이며 출발지,목적지에 따른 값만 넣어주면된다.

1 =>1 (값없음) , 1=>2 (0+47) , 2=>1 (47) , 2=>2 (47) , 2=>3 (47) , 2=>4 (47+57) , 4=>1 (104) ...

 

 

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>

using namespace std;

int N, M;
int visit[11];
int lv = 0x7fffffff;
int W[11][11];

void dfs(int s, int v) {
    if (s == N) {
        if (lv > v) {
            lv = v;
            return;
        }
    }

    for (int i = 1; i <= N; i++) {
        if (visit[i] == 0 && W[s][i] != 0) {
            visit[i] = 1;
            dfs(i, v + W[s][i]);
            visit[i] = 0;
        }
    }
}

int main() {
    int s, e, v;
    int value = 0;

    scanf("%d %d", &N, &M);

    for (int i = 0; i < M; i++) {
        scanf("%d %d %d", &s, &e, &v);
        W[s][e] = W[e][s] = v;
    }

    dfs(1, value);

    printf("%d", lv == 0x7fffffff ? -1 : lv);

    return 0;
}

 

 

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>

using namespace std;

int N, M;
int visit[11];
int lv = 0x7fffffff;
vector<int> W[101];

void dfs(int s, int v) {
    if (s == N) {
        if (lv > v) {
            lv = v;
            return;
        }
    }

    for (int i = 0; i < W[s].size(); i += 2) {
        if (visit[W[s][i]] == 0) {
            visit[W[s][i]] = 1;
            dfs(W[s][i], v + W[s][i + 1]);
            visit[W[s][i]] = 0;
        }
    }
}

int main() {
    int s, e, v;
    int value = 0;

    scanf("%d %d", &N, &M);

    for (int i = 0; i < M; i++) {
        scanf("%d %d %d", &s, &e, &v);

        // 간선 정보를 저장
        W[s].push_back(e);
        W[s].push_back(v);

        W[e].push_back(s);
        W[e].push_back(v);
    }

    dfs(1, value);

    printf("%d", lv == 0x7fffffff ? -1 : lv);

    return 0;
}