[백준/Python] 14889번 - 스타트와 링크

문제

백준 14889번 - 스타트와 링크

해결 과정

• 백트래킹을 이용한다.

• 스타트팀과 링크팀은 n//2 로 나눠지니까 그 조건을 기준으로 스타트팀에 없는 인덱스를 링크팀에 넣고 능력치를 계산한다.

  • 그 능력치가 최소보다 작다면 min_diff 에 할당
  • 다른 경우의 수를 계산해야하니까 link.clear

• index != n//2 라면

  • 0 ~ n 까지 스타트팀에 있는지 확인
  • 스타트팀이 비워있지 않고 스타트팀의 마지막 사람이 i보다 큰지 확인
    🟰🟰 스타트팀의 마지막 사람이 i보다 크다는 것은 이미 들어갔다 왔던 사람이라는 것, 이미 방문했다는 개념과 비슷
  • 위 조건이 다 맞지 않다면
  • 스타트팀에 넣어주고 다른 경우의 수를 위해 dfs(index+1)

  

시행착오

• 이해하는데 오래걸렸다

풀이

import sys

n = int(sys.stdin.readline())

graph = []
start = []
link = []

for _ in range(n):
  graph.append(list(map(int,sys.stdin.readline().split())))

# 1000000000
min_diff = int(1e9)

def dfs(index):
  global min_diff
  # 재귀 탈출 조건 = 백트래킹 탑 체크 시점
  if index == n//2:
    Spower,Lpower = 0,0
    # 스타트팀에 없으면 링크팀에 넣기
    for i in range(n):
      if i not in start:
        link.append(i)
    # 각 팀의 능력치 구하기
    for i in range(n//2-1):
      for j in range(i+1,n//2):
        Spower += graph[start[i]][start[j]] + graph[start[j]][start[i]]
        Lpower += graph[link[i]][link[j]] + graph[link[j]][link[i]]
    diff = abs(Spower-Lpower)
    
    # 능력치가 최소인지 확인
    if min_diff > diff:
      min_diff = diff
    # 링크팀은 계산이 끝나면 항상 비워준다.
    link.clear()
    return
  
  # dfs
  for i in range(n):
    if i in start:
      continue
    # 스타트팀이 존재한다는 것
    # 스타트팀의 마지막 사람이 i보다 크다는 것은 이미 들어갔다왔던 (계산했던) 것이라는 뜻
    if len(start) > 0 and start[len(start)-1] > i:
      continue
    start.append(i)
    dfs(index+1)
    # return하고 여기로 돌아온다.
    # 마지막은 다시 빼줘야한다 다른 경우의 수를 넣어야하기 때문에
    start.pop()


dfs(0)
print(min_diff)