14889번: 스타트와 링크

문제링크

C++ 1st try

#include <iostream>
#include <vector>

using namespace std;

int N, S[20][20];

int ret_min = 1000000000;

int check_board[20];

void solve(){
    int ptr_start = 0, ptr_link = 0;

    vector <int> member_start, member_link;

    for (int i = 0; i < N; i++){
        if (check_board[i] == 1){
            member_start.push_back(i);
        }else{
            member_link.push_back(i);
        }
    }
    for (auto i : member_start){
        for (auto j : member_start){
            if (i != j){
                ptr_start += S[i][j];
            }
        }
    }
    for (auto i : member_link){
        for (auto j : member_link){
            if (i != j){
                ptr_link += S[i][j];
            }
        }
    }
    int diff;
    if (ptr_start > ptr_link)
        diff = ptr_start - ptr_link;
    else
        diff = ptr_link - ptr_start;
    if (diff < ret_min)
        ret_min = diff;
}

void fun(int cnt, int idx){
    if (cnt == N / 2)
        solve();
    for (int i = idx + 1; i < N; i++){
        check_board[i] = 1;
        fun(cnt + 1, i);
        check_board[i] = 0;
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++){
        for (int j = 0; j < N; j++){
            cin >> S[i][j];
        }
    }
    fun(0, -1);
    cout << ret_min << "\n";
}

C++ 2nd try

#include <iostream>
#include <vector>

using namespace std;

int N, S[20][20];

int ret_min = 1000000000;

vector<int> board;

void solve(){
    int ptr_start = 0, ptr_link = 0;

    for (int i = 0; i < N / 2 - 1; i++){
        for (int j = i + 1; j < N / 2; j++){
            ptr_start += S[board[i]][board[j]] + S[board[j]][board[i]];
        }
    }

    int rem[20];
    for (int i = 0; i < 20; i++){
        rem[i] = 0;
    }
    for (auto a : board){
        rem[a] = 1;
    }
    vector<int> rem_board;
    for (int i = 0; i < 20; i++){
        if (rem[i] == 0)
            rem_board.push_back(i);
    }
    for (int i = 0; i < N / 2 - 1; i++){
        for (int j = i + 1; j < N / 2; j++){
            ptr_link += S[rem_board[i]][rem_board[j]] + S[rem_board[j]][rem_board[i]];
        }
    }
    int diff;
    if (ptr_start > ptr_link)
        diff = ptr_start - ptr_link;
    else
        diff = ptr_link - ptr_start;
    if (diff < ret_min)
        ret_min = diff;
}

void fun(int idx){
    if (idx == N)
        return ;
    if (board.size() == N / 2)
        solve();
    board.push_back(idx);
    fun(idx + 1);
    board.pop_back();
    fun(idx + 1);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++){
        for (int j = 0; j < N; j++){
            cin >> S[i][j];
        }
    }
    fun(0);
    cout << ret_min << "\n";
}

Python 1st try

import sys
input = sys.stdin.readline

N = int(input())
S = []
for _ in range(N):
    S.append(list(map(int, input().split())))


check_board = [0] * N

ret_min = 1000000

def solve():
    global ret_min, N, S, check_board
    ptr_start = 0
    ptr_link = 0
    member_start = []
    member_link = []

    for i in range(N):
        if check_board[i] == 1:
            member_start.append(i)
        else:
            member_link.append(i)
    for i in member_start:
        for j in member_start:
            if i != j:
                ptr_start += S[i][j]
    for i in member_link:
        for j in member_link:
            if i != j:
                ptr_link += S[i][j]
    if ptr_start > ptr_link:
        diff = ptr_start - ptr_link
    else:
        diff = ptr_link - ptr_start
    if diff < ret_min:
        ret_min = diff


def fun(cnt, idx):
    global N, S, check_board
    if cnt == N / 2:
        solve()
    for i in range (idx + 1, N):
        check_board[i] = 1
        fun(cnt + 1, i)
        check_board[i] = 0

fun(0, -1)

print(ret_min)

Python 2nd try

import sys
input = sys.stdin.readline

N = int(input())
S = []
for _ in range(N):
    S.append(list(map(int, input().split())))


my_start = []

ret_min = 1000000

def solve():
    global ret_min, N, S
    ptr_start = 0
    ptr_link = 0
    my_link = []

    for i in range(0, N // 2 - 1):
        for j in range(i + 1, N // 2):
            ptr_start += S[my_start[i]][my_start[j]] + S[my_start[j]][my_start[i]]
    check_board = [0] * N
    for i in my_start:
        check_board[i] = 1
    for i in range(0, N):
        if check_board[i] == 0:
            my_link.append(i)

    for i in range(0, N // 2 - 1):
        for j in range(i + 1, N // 2):
            ptr_link += S[my_link[i]][my_link[j]] + S[my_link[j]][my_link[i]]

    if ptr_start > ptr_link:
        diff = ptr_start - ptr_link
    else:
        diff = ptr_link - ptr_start
    if diff < ret_min:
        ret_min = diff


def fun(idx):
    global N, S
    if idx == N:
        return
    if len(my_start) == N / 2:
        solve()
        return

    my_start.append(idx)
    fun(idx + 1)
    my_start.pop(len(my_start) - 1)
    fun(idx + 1)

fun(0)

print(ret_min)

• 다른 사람 풀이를 참고하여 2nd try로 수정하였다.
  • 백트래킹으로 combination마다 브루트포스를 해야하는 문제를 또 보게 되면 처음 풀이처럼 복잡한 for문을 쓰지 말고,
  • 파이썬의 list, cpp의 vector에 push한 후 다음 인덱스로 재귀를 하고 리턴하여 pop한 후 다시 한 번 다음 인덱스로 재귀를 하는 방식을 쓰면 좋을듯하다.
• C로 풀 때 순열로 풀고 이번에 풀 때는 재귀로 풀었는데 순열로 풀게 되면 Cpp의 next_permutation을 사용하는 것도 좋을 것 같다.
• $O(2^{N} * N^{2})$