[백준] 14889번: 스타트와 링크 - python

문제 출처

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

14889번: 스타트와 링크

 

 

 

---

풀이 및 코드

필자는 해당 문제를 처음 봤을 때는 아무래도 시간초과가 걱정 됐다. 모든 데이터를 살피고 계산까지 하려면 완전 탐색(bfs, dfs)보다는 dp를 이용해 문제를 풀어야 한다고 생각했고 이런 저런 고민을 해보았지만 딱히 떠오르지 않아 완전 탐색(bfs, dfs)으로 접근해 문제를 해결하였다. bfs(deque)와  dfs(재귀) 두가지 방법으로 풀어보았고 그 풀이를 포스팅 하고자 한다.

 

 

 

 BFS(deque)

나눠질 두 팀을 left, right라고 하자. 0번부터 n-1까지 한명씩 돌면서 팀을 배정하고 현재 상황을 dq에 저장하는 방식으로 bfs를 진행하였다. dq에 저장되는 값은 길이가 4인 1차원 배열로 [left팀, right팀, left팀 능력치 합, right팀 능력치 합]으로 저장했다. 특정 팀에 선수가 n/2보다 적을 때에만 선수를 추가해 주었으며 능력치 계산은 새로운 선수가 주어질 때마다 능력치의 합을 생신했다.

 

	from collections import deque
	n = int(input())
	stats = [list(map(int, input().split())) for _ in range(n)]
	answer = float("inf")
	# [left팀, right팀, left팀 능력치 합, right팀 능력치 합]
	dq = deque([[[0],[],0,0], [[],[0],0,0]])
	for i in range(1, n):
	for _ in range(len(dq)):
	l, r, lv, rv = dq.popleft()
	# left팀의 선수가 n/2보다 작다면 선수 제공 및 능력치 업데이트
	if len(l) < n / 2:
	# 선수가 2명이 안된다면 능력치 업데이트 불가
	if len(l) < 1:
	dq.append([l + [i], r, lv, rv])
	else:
	new_lv = lv
	for ll in l:
	new_lv += (stats[ll][i] + stats[i][ll])
	dq.append([l + [i], r, new_lv, rv])
	# right팀의 선수가 n/2보다 작다면 선수 제공 및 능력치 업데이트
	if len(r) < n / 2:
	# 선수가 2명이 안된다면 능력치 업데이트 불가
	if len(r) < 1:
	dq.append([l, r + [i], lv, rv])
	else:
	new_rv = rv
	for rr in r:
	new_rv += (stats[rr][i] + stats[i][rr])
	dq.append([l, r + [i], lv, new_rv])
	else:
	# 모든 선수들의 팀 배치가 끝났다면 가장 작은 차이 출력
	for l, r, lv, rv in dq:
	res = abs(lv - rv)
	answer = res if res < answer else answer
	print(answer)

view raw 14889(bfs).py hosted with ❤ by GitHub

 

 

 DFS(재귀)

해당 방식은 def dfs(i, left)와 def calculation(i, left)  두 함수를 사용해 구현하였다. dfs 함수는 i번째 선수를 받아 팀을 선택하도록 만들고 만일 두 팀중 한팀이라도 n/2명이 다 채워지면 calculation을 호출한다. calculation함수는 각 선수들을 모아 능력치의 합을 계산해 answer을 업데이트 하는 함수이다.

 

	from collections import deque
	from itertools import combinations
	n = int(input())
	stats = [list(map(int, input().split())) for _ in range(n)]
	answer = float("inf")
	def calculation(i, left):
	global answer
	# 나머지 선수들의 팀 선택 및 right 팀 구성
	if len(left) != n/2:
	left += [v for v in range(i, n)]
	right = [v for v in range(n) if v not in left]
	# 각 팀의 능력치 총합 구하기
	sum_left = 0
	sum_right = 0
	for j, k in combinations(left,2):
	sum_left += stats[j][k] + stats[k][j]
	for j, k in combinations(right,2):
	sum_right += stats[j][k] + stats[k][j]
	# 능력치 총합의 차 구하기
	res = abs(sum_right - sum_left)
	answer = res if res < answer else answer
	def dfs(i, left):
	# 만일 left 혹은 right의 팀이 모두 채워졌다면
	if len(left) == n/2 or i - len(left) == n/2:
	calculation(i, left)
	return
	# left팀과 right팀에 선수 추가
	dfs(i+1, left + [i])
	dfs(i+1, left)
	dfs(0, [])
	print(answer)

view raw 14889(dfs).py hosted with ❤ by GitHub

 

 

해당 문제는 삼성 기출 문제로 silver2에 배치되어 있다.