[백준 / BOJ] 14889번 스타트와 링크 (C++, Python)

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

14889번: 스타트와 링크

---

문제

---

문제 풀이

백트래킹 문제이며, 우선 팀을 반으로 어떻게 나눌까? 하는 생각에서 출발하게 된다.  

 

C++ 상세 풀이

2차원 벡터에 행렬을 담아주었다. N이 4에서 20까지이므로 visited 배열을 크기 20으로 설정해 전역으로 선언해두었다.

 

C++ 코드

void dfs(std::vector<std::vector<int>> &v, int cur, int idx) {
    // cur이 N / 2와 같다면 한 팀에 총 인원의 반이 담겨졌다는 의미이므로 멈추고 능력치의 차이를 계산함.
    if (cur == N / 2) {
        int res1 = 0, res2 = 0;

        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                // visited[i]가 true인 사람과 false인 사람으로 나눠지므로 능력치를 더하면 됨.
                if (visited[i] && visited[j])
                    res1 += v[i][j];
                else if (!visited[i] && !visited[j])
                    res2 += v[i][j];
            }
        }

        res = std::min(res, abs(res1 - res2));
        return;
    }
        
    // idx부터 탐색, 만약 i가 방문하지 않았다면 아무런 팀에 담겨있지 않다는 뜻이므로 i + 1인자를 넘겨줘 다음 사람부터 탐색하도록 함.
    for (int i = idx; i < N; ++i) {
        if (!visited[i]) {
            visited[i] = true;
            dfs(v, cur + 1, i + 1);
            visited[i] = false;
        }
    }
}

dfs 인자로는 벡터, cur, idx가 들어간다. 여기서 cur은 현재 한 팀에 몇명이 담겼는지, idx는 visited 부분을 보면 알겠지만 이미 방문한 사람을 visited[i] 검사할 필요가 없으므로 다음 사람부터 인자로 넘겨준다.

 

만약 cur이 N / 2와 같다면 한 팀이 만들어졌다는 의미이므로, 능력치의 차이를 계산해주기 시작한다. 여기서 visited[i]가 true인 사람, false인 사람으로 반반 나누어지므로 해당 능력치를 더해주면 된다.

Python 상세 풀이

2차원 리스트에 행렬을 담아주었다. visited는 입력받은 N의 크기만큼 리스트로 미리 만들어두었다.

Python 코드

def dfs(cur, idx):
    global res

    # cur이 N // 2와 같다면 한 팀에 총 인원의 반이 담겨졌다는 의미이므로 멈추고 능력치의 차이를 계산함.
    if cur == N // 2:
        res1, res2 = 0, 0
        for i in range(N):
            for j in range(N):
                # visited[i]가 true인 사람과 false인 사람으로 나눠지므로 능력치를 더하면 됨.
                if visited[i] and visited[j]:
                    res1 += arr[i][j]
                elif not visited[i] and not visited[j]:
                    res2 += arr[i][j]

        res = min(res, abs(res1 - res2))
        return

    # idx부터 탐색, 만약 i가 방문하지 않았다면 아무런 팀에 담겨있지 않다는 뜻이므로 i + 1인자를 넘겨줘 다음 사람부터 탐색하도록 함.
    for i in range(idx, N):
        if not visited[i]:
            visited[i] = True
            dfs(cur + 1, i + 1)
            visited[i] = False

dfs 인자로는 cur, idx가 들어간다. 여기서 cur은 현재 한 팀에 몇명이 담겼는지, idx는 visited 부분을 보면 알겠지만 이미 방문한 사람을 visited[i] 검사할 필요가 없으므로 다음 사람부터 인자로 넘겨준다.

 

만약 cur이 N / 2와 같다면 한 팀이 만들어졌다는 의미이므로, 능력치의 차이를 계산해주기 시작한다. 여기서 visited[i]가 true인 사람, false인 사람으로 반반 나누어지므로 해당 능력치를 더해주면 된다.

 

C++ 코드 전문

Python 코드 전문

 

소감

처음에 문제를 제대로 보지 않았다가 2명씩 짝짓는 줄 알고 삽질을 조금 했었다. 문제와 조건을 잘 읽어야겠다는 생각이 들었다.