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

출처 : 백준, https://www.acmicpc.net/problem/14889

14889번: 스타트와 링크

 

 

풀이

 

from itertools import combinations

def calTeamScore(team, matrix):
  sum = 0

  for i in range(0, len(team)):
    for j in range(i, len(team)):
      sum += matrix[team[i]][team[j]] + matrix[team[j]][team[i]]

  return sum

if __name__ == '__main__':
  matrix = []
  n = int(input())

  for i in range(n):
    matrix.append(list(map(int, input().split())))

  p_combi = combinations([i for i in range(n)], n//2)
  min_val = 99999

  for team in p_combi:
    if team not in visited:
      op_team = dict([(i, i) for i in range(n)])
      for mem in team:
        del(op_team[mem])

      diff = abs(calTeamScore(team, matrix) - calTeamScore(list(op_team), matrix))

      if diff < min_val:
        min_val = diff

  print(min_val)

 

원래 중복제거를 염두해두고 풀이를 짰다가 깜빡하고 안 넣은 풀이인데 5712ms가 걸렸다.

근데 통과하더라? 왜지?

로직은 다음과 같다.

 

1. 팀을 n//2명으로 구성한 조합을 생성

2. 각 팀에 대해 모든 팀 점수 합산

3. 합산 시, 상대 팀도 구해서 합산 후 차를 구함

4. 최솟값일 경우 갱신

 

아래 풀이는 dict 자료형을 이용해 방문체크를 해준 것만 바뀌었다. 이 경우에는 3200ms가 걸린다.

dict 자료형의 key로는 list나 dict은 안되고 오직 tuple만 key로 사용할 수 있다.

 

from itertools import combinations

def calTeamScore(team, matrix):
  sum = 0

  for i in range(0, len(team)):
    for j in range(i, len(team)):
      sum += matrix[team[i]][team[j]] + matrix[team[j]][team[i]]

  return sum

if __name__ == '__main__':
  matrix = []
  n = int(input())
  visited = dict()

  for i in range(n):
    matrix.append(list(map(int, input().split())))

  p_combi = combinations([i for i in range(n)], n//2)
  min_val = 99999

  for team in p_combi:
    if team not in visited:
      op_team = dict([(i, i) for i in range(n)])
      for mem in team:
        del(op_team[mem])

      visited[team] = 1
      visited[tuple(op_team)] = 1

      diff = abs(calTeamScore(team, matrix) - calTeamScore(list(op_team), matrix))

      if diff < min_val:
        min_val = diff

  print(min_val)

---

 

시간 복잡도

 

-

 

다른 사람의 풀이를 보면서 알게 된 점

 

보니까 알고리즘에 백트래킹이 있더라.

알아보고 추가 예정

 

고찰

 

완전탐색 같아서 중복제거를 염두해두고 시작했는데

실수로 안하고 들어간 풀이가 성공해서 놀랐다.

dict 자료형이 아니라 어설프게 list에서 in 연산자로 방문체크를 하니까 오히려 시간초과가 나오더라.

방문체크하는 시간이 너무 길어져서 배보다 배꼽이 커진 경우가 아닌가 싶다.

그리고 방문체크하는 부분을 작성하면서 알게 된 것인데,

dict 자료형의 key로는 list나 dict은 안되고 오직 tuple만 key로 사용할 수 있다.