[Inflearn] 최소비용(DFS : 인접행렬 사용)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

인접행렬에 가중치를 저장한 후,

방문과 마찬가지로 완전탐색을 하면서 가중치를 더해나가면 될 것 같다.

마지막에 sum 은 rst 와 비교해서 최솟값으로 저장하고!

	1	2	3	4	5
1	0	12	6	10	0
2	0	0	2	0	2
3	0	0	0	3	0
4	0	2	0	0	5
5	0	0	0	0	0

먼저 DFS(1, 0) 을 넣어준다.

D(1, 0)

종료 조건은 v 가 n 이 될 경우, sum 을 rst 와 비교해서 

최소 rst 를 저장하는 것

1부터 5까지 연결된 정점을 찾아야하므로

void DFS(int v, int sum)

{

if(v == n)

{

if(rst > sum)

rst = sum;

}

else

{

for(i = 1; i <= n; i++)

{

if(map[v][i] > 0 && ch[i] == 0)

{

ch[i] = 1;

DFS(i, sum + map[v][i]);

ch[i] = 0;

}

}

}

}

1 부터 연결된 정점을 찾는다.

정점 2와 가중치 12로 연결되어있다.

1	2	3	4	5
1	1

D(2, 12)

D(1, 0)

2 지점과 연결된 정점은 3과 5인데 3 먼저,

2 지점은 3지점과 가중치 2로 연결되어잇다.

1	2	3	4	5
1	1	1

D(3, 14)

D(2, 12)

D(1, 0)

정점 3은 정점 4하고만 가중치 3으로 연결되어있다.

1	2	3	4	5
1	1	1	1

D(4, 17)

D(3, 14)

D(2, 12)

D(1, 0)

정점 4는 2와 5로 연결되어있는데,

정점 2는 이미 방문하였으므로 5로 이동한다. 가중치는 5

1	2	3	4	5
1	1	1	1	1

D(5, 22)

D(4, 17)

D(3, 14)

D(2, 12)

D(1, 0)

정점 5에 도착하였으니 rst 와 최솟값을 비교하여 저장한다.

...

스택을 그리면서 과정을 생각해보니까 갈수록 재귀함수를 구현해내는 속도가 빨라지는 것 같다.

신이난다~!

#. Code

#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int n, m, rst = 2147000000;
int map[21][21], ch[21];
 
void DFS(int v, int sum)
{
    int i;
 
    if (v == n)
    {
        if (rst > sum)
            rst = sum;
    }
    else
    {
        for (i = 1; i <= n; i++)
        {
            if (map[v][i] > 0 && ch[i] == 0)
            {
                ch[i] = 1;
                DFS(i, sum + map[v][i]);
                ch[i] = 0;
            }
        }
    }
}
 
int main(void)
{
    freopen("input.txt", "rt", stdin);
 
    int i, a, b, w;
 
    scanf("%d %d", &n, &m);
 
    for (i = 0; i < m; i++)
    {
        scanf("%d %d %d", &a, &b, &w);
 
        map[a][b] = w;
    }
 
    ch[1] = 1;
 
    DFS(1, 0);
 
    printf("%d\n", rst);
 
    return 0;
}

풀이 과정에서 설명했던 그대로 구현하였다.

앞전에 풀었던 문제들과 비슷해서 금방 풀 수 있었던 것 같다.

이제 슬슬 잘 풀린다고 거만해지지 말자!

#. Other code

#include<stdio.h>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int map[30][30], ch[30], n, cost=2147000000;    
 
void DFS(int v, int sum){
    int i;
 
    if(v==n){
        if(sum<cost) cost=sum;
    }
    else{
        for(i=1; i<=n; i++){
            if(map[v][i]>0 && ch[i]==0){
                ch[i]=1;
                DFS(i, sum+map[v][i]);
                ch[i]=0;
            }
        }
    }
}
 
int main(){
    int m, i, a, b, c;
    scanf("%d %d", &n, &m);
    for(i=1; i<=m; i++){
        scanf("%d %d %d", &a, &b, &c);
        map[a][b]=c;
    }
    ch[1]=1;
    DFS(1, 0);
    printf("%d\n", cost);
    
    return 0;
}

초반 1부터의 과정을 그림으로 그려보면 아래와 같다.

나중에 익숙해지면 머릿속으로 그려가면서 할 수 있겠지만

아직은 그림을 그리면서 하는게 너무 편하다. 하핳

언젠가는 머릿속으로 바로 풀어낼 수 있겠지..!

#. Result

  - Input --------------------------------------------------------

5 8 

1 2 12 

1 3 6 

1 4 10

2 3 2

2 5 2 

3 4 3 

4 2 2 

4 5 5

------------------------------------------------------------------

  - Output --------------------------------------------------------

13

------------------------------------------------------------------