[백준 / 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++ 코드 전문

	#include <algorithm>
	#include <iostream>
	#include <vector>
	#include <cmath>
	int N;
	bool visited[20];
	int res = 201;
	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;
	}
	}
	}
	void init() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	}
	int main() {
	init();
	std::cin >> N;
	std::vector<std::vector<int>> v(N, std::vector<int>(N, 0));
	for (int i = 0; i < N; ++i)
	for (int j = 0; j < N; ++j)
	std::cin >> v[i][j];
	dfs(v, 0, 0);
	std::cout << res << "\n";
	return 0;
	}

view raw 14889_스타트와 링크 (22.08.06 성공).cpp hosted with ❤ by GitHub

Python 코드 전문

	import sys
	input = sys.stdin.readline
	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
	if __name__ == "__main__":
	res = 201
	N = int(input())
	arr = [list(map(int, input().split())) for _ in range(N)]
	visited = [False] * N
	dfs(0, 0)
	print(res)

view raw 14889_스타트와 링크 (22.08.06 성공).py hosted with ❤ by GitHub

 

소감

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