🚩 문제 설명
https://www.acmicpc.net/problem/14889
⏱️ 시간 복잡도
▪log(N) x N^2
◾ 짝수의 사람을 두개의 팀으로 나눕니다.
◾ 사람마다 각각 팀원들마다 같은 팀이 되었을 때 시너지 능력치가 있습니다.
◾ 두 팀의 능력치를 구하고, 차가 제일 작은 값을 구하는 문제입니다.
✅ 입출력
n : 총 사람의 수 (짝수) s(1) ~ s(n) : n개의 줄, n개의 수 return 스타트 팀과 링크 팀의 능력치 차이의 최솟값
✔️ 예제 1
4
0 1 2 3
4 0 5 6
7 1 0 2
3 4 5 0
0
✔️ 예제 2
6
0 1 2 3 4 5
1 0 2 3 4 5
1 2 0 3 4 5
1 2 3 0 4 5
1 2 3 4 0 5
1 2 3 4 5 0
2
✔️ 예제 3
8
0 5 4 5 4 5 4 5
4 0 5 1 2 3 4 5
9 8 0 1 2 3 1 2
9 9 9 0 9 9 9 9
1 1 1 1 0 1 1 1
8 7 6 5 4 0 3 2
9 1 9 1 9 1 0 9
6 5 4 3 2 1 9 0
1
시간초과 코드
import sys
sys.stdin = open('input2.txt', 'rt')
input = sys.stdin.readline
n = int(input()) # 사람의 총수
s = [list(map(int, input().split())) for _ in range(n)] # 능력치맵
team = [0] * n
visited = []
# 능력치 계산하기
def check_ability():
global ans
sum1, sum2 = 0, 0
ones = [i for i in range(n) if team[i]]
zeros = [i for i in range(n) if not team[i]]
if ones in visited or zeros in visited:
return -2147000, 2147000
visited.append(ones)
visited.append(zeros)
# 스타트팀
for i in range(n // 2):
for j in range(i + 1, n // 2):
sum1 += (s[ones[i]][ones[j]] + s[ones[j]][ones[i]])
# 링크팀
for i in range(n // 2):
for j in range(i + 1, n // 2):
sum2 += (s[zeros[i]][zeros[j]] + s[zeros[j]][zeros[i]])
return sum1, sum2
# 백트랙킹
def dfs(cnt):
global ans
# 반으로 팀이 구성되어졌다면
if cnt == n // 2:
sum1, sum2 = check_ability()
ans = min(ans, abs(sum1 - sum2))
return
for i in range(n):
if team[i]: # 팀을 구성했다면
continue
team[i] = 1 # 팀구성 처리
dfs(cnt + 1) # cnt: 팀 구성원 명수
team[i] = 0 # 벡트랙킹
if __name__ == '__main__':
ans = 2147000000
dfs(0)
print(ans)
📑 문제 풀이
with 파이썬 (Python) 2시간
import sys
sys.stdin = open('input2.txt', 'rt')
input = sys.stdin.readline
n = int(input()) # 사람의 총수
visited = [0] * n # 1, 0 으로 팀을 나눈다.
s = [list(map(int, input().split())) for _ in range(n)] # 능력치맵
def dfs(depth, idx):
global ans
# 만약 사람이 두 팀으로 나눠졌다면
if depth == n // 2:
sum1, sum2 = 0, 0
# 브루트포스: 전부를 확인한다
for i in range(n):
for j in range(n):
if visited[i] and visited[j]: # 0
sum1 += s[i][j]
elif not visited[i] and not visited[j]: # 1
sum2 += s[i][j]
# 최솟값을 구한다
ans = min(ans, abs(sum1 - sum2))
return
# 백트랙킹
# idx를 둬서 시간을 줄인다.
for i in range(idx, n):
if not visited[i]:
visited[i] = 1 # 방문 처리
dfs(depth + 1, i + 1)
visited[i] = 0 # 백트랙킹
if __name__ == '__main__':
ans = 2147000000
dfs(0, 0)
print(ans)
💬 Point
➡️ DFS() 사용
➡️ 브루트포스를 이용하여 꾸려진 팀원 각각을 비교하여 돈다.
◾ pypy3 로 제출해야 시간초과가 나지 않고 정답으로 나옵니다.
◾ 쉽게 합을 풀 수 있는 문제였는데 왜 이렇게 어렵게 생각했을까요
input = sys.stdin.readline
n = int(input()) # 사람의 총수
visited = [0] * n # 1, 0 으로 팀을 나눈다.
s = [list(map(int, input().split())) for _ in range(n)] # 능력치맵
◾ 입력을 받습니다.
# 백트랙킹
# idx를 둬서 시간을 줄인다.
for i in range(idx, n):
if not visited[i]:
visited[i] = 1 # 방문 처리
dfs(depth + 1, i + 1)
visited[i] = 0 # 백트랙킹
◾ 우선, 백트랙킹을 셀 for 문을 만들어줍니다.
idx 를 이용해서 시간을 줄여줄 수 있습니다. 만약 방문을 했다면 넘겨지고, 방문을 하지 않았다면 방문 처리를 해줍니다.
그리고 다음 depth 로 넘어갑니다. depth 는 한팀에 꾸려지는 사람 수를 이릅니다.
만약 return 이 되면 방문 처리를 한 것을 다시 0으로 만듭니다. 백트랙킹을 합니다.
# 만약 사람이 두 팀으로 나눠졌다면
if depth == n // 2:
sum1, sum2 = 0, 0
# 브루트포스: 전부를 확인한다
for i in range(n):
for j in range(n):
if visited[i] and visited[j]: # 0
sum1 += s[i][j]
elif not visited[i] and not visited[j]: # 1
sum2 += s[i][j]
# 최솟값을 구한다
ans = min(ans, abs(sum1 - sum2))
return
◾ 만약 팀이 두개로 나눠진다면, 브루트포스를 돌아 어느 사람이 1이고 0 인지 확인을 합니다.
해당 두 개의 for문은 (0, 0), (0, 1), (0, 2) .. 이런 식으로 주어진 인덱스의 숫자를 하나하나 다 돕니다.
하나하나 다 돌아서 만약 둘 다 visited 되어 있다면 능력치를 더하게 됩니다.
그러면 스타트팀이 구해지고, 방문처리가 되지 않은 값들은 자연스럽게 다른 팀이 되어 링크팀의 능력치 총합이 됩니다.
그리고나서 min() 을 통해서 최솟값을 구합니다.
abs() 를 이용하여 절댓값을 구하여 비교를 해야합니다. 그리고 재귀에서 빠져나올 수 있도록 return 을 해줍니다.
if __name__ == '__main__':
ans = 2147000000
dfs(0, 0)
print(ans)
◾ 메인 함수 입니다.
# 알고리즘 백준 스타트와링크 dfs python 파이썬
# 알고리즘 백준 스타트와 링크 python dfs 파이썬
'✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺 > 백준 알고리즘' 카테고리의 다른 글
[BJ1244] 스위치 켜고 끄기 (0) | 2022.08.01 |
---|---|
[BJ2309] 일곱 난쟁이 (0) | 2022.08.01 |
[BJ14888] 연산자 끼워넣기 (0) | 2022.05.11 |
[BJ14503] 로봇 청소기 (0) | 2022.05.07 |
[BJ14502] 연구소 (0) | 2022.05.04 |