[백준/BOJ/알고리즘/파이썬(Python)/C++]#14889_스타트와 링크

https://www.acmicpc.net/problem/14889

14889번: 스타트와 링크

파이썬은 combinations라는 아주 편~한 라이브러리로 코딩할 수 있다.(파이썬최고)

start를 먼저 배정하고 나머지 빈 배열에 link를 배정하였다.

 

파이썬 코드

import sys
from itertools import combinations
input=sys.stdin.readline

arr = []
N = int(input())

for i in range (N):
    arr.append(list(map(int,input().split())))

num_list = [i for i in range(N)]
output = 100 + 100 
for cases_start in (combinations(num_list, N//2)):
    start=0
    link=0
    for i in cases_start:
        for j in cases_start:
            start += arr[i][j]
    cases_link = [i for i in range(N) if i not in cases_start]
    for i in cases_link:
        for j in cases_link:
            link += arr[i][j]
    output = min(output, abs(start-link))
print(output)

 

C++로 하면 좀 더 복잡한데, 백트래킹 문제로 반복으로 상향식으로 풀려고 계속 시도했으나 실패해서

결국 재귀로 하향식으로 풀었다.

 

 

아무래도 중복제거가 어디가 안되서 계산을 더 하는 것 같다. 시간적 비용을 줄이려고 반복으로 어떻게든 풀어내고 싶었는데, 시간에 쫓겨 결국 재귀로 공사했다.

 

실패한 코드

#include<iostream>
#include<vector>
#include<cmath>
#define MAX 20
using namespace std;
int main(){
	int N;
	int output=100+100;
	bool visited[MAX+1]={false};
	int arr[MAX+1][MAX+1]={0};
	cin>>N;
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++)
			cin>>arr[i][j];
	}
	vector<int> cases_start;
	vector<int> cases_link;
	int start=0;
	int link=0;
	int cnt=0;
	for(int idx=0;idx<N;idx++){
		if(visited[idx]){
			continue;
		}
		else{
			visited[idx]=true;
			if(cnt==(N/2)){
				for(int i=0;i<N;i++){
					if(visited[i]==true)
						cases_start.push_back(i);
					else
						cases_link.push_back(i);
				}				
				for(int i=0;i<(N/2);i++){
					for(int j=0;j<(N/2);j++){
						start+=arr[cases_start[i]][cases_start[j]];
						link+=arr[cases_link[i]][cases_link[j]];
					//	cout<<cases_start[i]<<endl;
					}
				}
				output=min(output, abs(start-link));
				cout<<output;
			}
			cnt+=1;
			visited[idx]=false;
		}
		
	}

			
}

C++ 성공한 코드_ 재귀(하향식_top down)

파이썬과 다르게 C++은 조합을 라이브러리로 할 수 없으므로 visited배열과 같이 다녀간 배열을 기록하여 조건문으로 달아 재귀를 돌린다.

#include<iostream>
#include<vector>
#include<cmath>
#define MAX 20
using namespace std;
int N;
int output=100*100;
bool visited[MAX+1]={false};
int arr[MAX+1][MAX+1]={0};
void startlink(int idx, int cnt){
	vector<int> cases_start;
	vector<int> cases_link;
	int start=0;
	int link=0;
	
	if(cnt==(N/2)){
		for(int i=0;i<N;i++){
			if(visited[i]==true)
				cases_start.push_back(i);
			else
				cases_link.push_back(i);
		}				
		for(int i=0;i<(N/2);i++){
			for(int j=0;j<(N/2);j++){
				start+=arr[cases_start[i]][cases_start[j]];
				link+=arr[cases_link[i]][cases_link[j]];
			}
		}
		if(abs(start-link)<output)
			output=abs(start-link);
		return;
	}
			
	for(int i=idx;i<N;i++){
		if(visited[i]){
			continue;
		}
		else{
			visited[i]=true;		
			startlink(i,cnt+1);
			visited[i]=false;
		}
		
	}
}
int main(){

	cin>>N;
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++)
			cin>>arr[i][j];
	}
	startlink(0,0);	
	cout<<output;	
}