[백준] 14889.스타트와 링크

벡터 시간 오래 걸릴까봐 안 쓰고 풀었는데

오히려 벡터 사용하니까 더 빠르다.

 

---

DFS로 접근 

 

- 벡터 대신 반복문 사용

시간  :  124ms

 

#include <iostream>
#define MAX 20

using namespace std;

int N;
int map [MAX][MAX]={0,};
int visited[20]={0,};
int MIN = 1e9;


void solve()
{
    int start=0;
    int link=0;
    
    for(int i=0;i<N;i++)
    {
        if(visited[i]==1){
            for(int j=0;j<N;j++)    if(visited[j]==1)   start+=map[i][j];
        }
        else{
            for(int j=0;j<N;j++)    if(visited[j]==0)   link+=map[i][j];
        }
    }
    
    int res = start > link ? start-link : link - start;
    if( MIN > res)  MIN = res;
    
}

void DFS(int cnt,int idx)
{
    if(cnt == N/2)
    {
        solve();
        return;
    }
    
    for(int i=idx;i<N;i++){
        if(visited[i]==0)
        {
            visited[i]=1;
            DFS(cnt+1,i+1);
            visited[i]=0;
        }
    }
}
int main(void)
{
    cin >> N;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++)
            scanf("%d",&map[i][j]);
    }
    
    DFS(0,0);
    cout << MIN;
    return 0;
}

 

 

 

 

- 벡터 사용 

시간 : 100ms

 

#include <iostream>
#include <vector>

#define MAX 20

using namespace std;

int N;
int map [MAX][MAX]={0,};
int visited[20]={0,};
int MIN = 1e9;


void solve()
{
    int start=0;
    int link=0;
    
    vector <int> s;
    vector <int> l;

    for(int i=0;i<N;i++)
    {
        if(visited[i])  s.push_back(i);
        else    l.push_back(i);
    }
    
    for(int i=0;i<N/2;i++)
    {
        for(int j=0;j<N/2;j++){
            start += map[s[i]][s[j]];
            link += map[l[i]][l[j]];
        }
    }
    
    int res = start > link ? start-link : link - start;
    if( MIN > res)  MIN = res;
    
}

void DFS(int cnt,int idx)
{
    if(cnt == N/2)
    {
        solve();
        return;
    }
    
    for(int i=idx;i<N;i++){
        if(visited[i]==0)
        {
            visited[i]=1;
            DFS(cnt+1,i+1);
            visited[i]=0;
        }
    }
}
int main(void)
{
    cin >> N;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++)
            scanf("%d",&map[i][j]);
    }
    
    DFS(0,0);
    cout << MIN;
    return 0;
}

 

다른분들 풀이 보니까 DFS 사용 안하고 0ms로도 풀던데 한번 참고해봐야겠다.

 

조언, 질문 환영입니다!

댓글 남겨주세요~