[BOJ] 백준 14889 스타트와 링크 (Swift)

문제

풀이

먼저, 스타트팀와 링크팀을 나누어 주어야 합니다.
스타트팀의 팀원들을 n / 2명을 뽑는다면, 자동으로 링크팀도 팀이 꾸려지게 됩니다.
저는 백트래킹을 사용해서 조합할 수 있는 팀을 구했습니다.

이제 팀이 나누어졌다면, 팀별로 능력치를 구해줬습니다.

1, 2, 3번이 팀이라면,
$S_{12}, S_{21}, S_{13}, S_{31}, S_{23}, S_{32}$의 능력치가 팀의 능력치 일 것입니다.

반복문을 사용해서 구해주었고,
팀간의 능력치의 차이의 최소값을 구해주면 끝 입니다.

소스코드

	struct Team {
	let start: [Int]
	let link: [Int]
	}
	let n = Int(readLine()!)!
	var graph: [[Int]] = []
	var team: [Team] = []
	for _ in 0..<n {
	graph.append(readLine()!.split(separator: " ").map { Int($0)! })
	}
	var visited = [Bool](repeating: false, count: n)
	func getTeam(index: Int, startTeam: [Int]) {
	if startTeam.count == n / 2 {
	let linkTeam = visited.enumerated().filter { !$0.element }.map { $0.offset }
	team.append(Team(start: startTeam, link: linkTeam))
	return
	}
	for i in index..<n {
	if !visited[i] {
	visited[i] = true
	getTeam(index: i, startTeam: startTeam + [i])
	visited[i] = false
	}
	}
	}
	getTeam(index: 0, startTeam: [])
	var answer = Int.max
	for t in team {
	var startScore = 0
	var linkScroe = 0
	for i in 0..<n / 2 - 1 {
	for j in i + 1..<n / 2 {
	startScore += graph[t.start[i]][t.start[j]]
	startScore += graph[t.start[j]][t.start[i]]
	linkScroe += graph[t.link[i]][t.link[j]]
	linkScroe += graph[t.link[j]][t.link[i]]
	}
	}
	answer = min(answer, abs(startScore - linkScroe))
	}
	print(answer)

view raw 스타트와 링크.swift hosted with ❤ by GitHub

후기

백트래킹을 사용해서 팀을 나눌 수 있었습니다.
팀을 나누었다면, 팀간의 능력치의 차이의 최소값만 구해주면 되는 문제였습니다.