글 읽기 - 46프로에서 틀립니다 ㅠㅠ

csh4096 4년 전 0

dfs로 start팀을 구하고 start팀원이 N/2가 되었을 때 link를 구하고 최소값을 구하게 됩니다.

통과되는 코드를 봐도 차이가 없어 보이는데 예외케이스 좀 알려 주시면 감사하겠습니다.!!

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int N, board[21][21], ans = 400004;


void cal(vector<int> person){
    
    int len = person.size();
    int tmp = 0;
    for(int p1 = 0; p1<len; p1++){
        for(int p2 = p1+1; p2<len; p2++){
            int person1 = person[p1];
            int person2 = person[p2];
            tmp += (board[person1][person2] + board[person2][person1]);
        }
    }
    bool visit[21] = {false, };
    vector<int> link;

    for(int i=0; i<len; i++)
        visit[person[i]] = true;

    for(int i=0; i<N; i++)
        if(!visit[i]) link.push_back(i);
    
    len = link.size();

    // for(int i=0; i<link.size(); i++)
    //     cout << link[i] << " ";
    // cout << endl;
    
    for(int p1 = 0; p1<len; p1++){
        for(int p2 = p1+1; p2<len; p2++){
            int person1 = link[p1];
            int person2 = link[p2];
            tmp -= (board[person1][person2] + board[person2][person1]);
        }
    }

    ans = min(abs(tmp), ans);
    // printf("%d\n", ans);

}
void dfs(vector<int> person, bool visit[21], int p){
    if(person.size() == N/2){
        // for(int i=0; i<person.size(); i++)
        //     cout << person[i] << " ";
        // cout << endl;
        cal(person);
        return ;
    }

    for(int i = p+1; i<N; i++){
        if(!visit[i]){
            person.push_back(i);
            visit[i] = true;
            dfs(person, visit, i);
            person.pop_back();
            visit[i] = false;
        }
    }
}
int main(){
    scanf("%d", &N);

    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            scanf("%d", &board[i][j]);
        }
    }

    bool visit[21];
    vector<int> arr;

    for(int i=0; i<N; i++){
        arr.push_back(i);
        visit[i] = true;
        dfs(arr, visit, i);
        arr.pop_back();
        visit[i] = false;
    }

    cout << ans << endl;
}

yehyun 4년 전 1

76줄에서 visit을 명시적으로 초기화해주지 않아도 전부 false로 초기화되나요?

csh4096 4년 전 1

와 고쳐서 제출하니 통과했습니다!!!

감사합니다!!!!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

46프로에서 틀립니다 ㅠㅠ

csh4096 4년 전 0

yehyun 4년 전 1

csh4096 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말