[백준] 스타트와 링크(Python) - 백트래킹

# 문제 

문제가 복잡해 보일 수 있지만, 사실 아래와 같은 diagonal 하게 대칭인 능력치 행렬이 주어지면, 두 팀의 능력치 차이가 최소가 되도록 팀을 나누고, 그 최소값을 반환하는 문제이다. 

 

# 입출력 

 

# Idea

이 문제는 생각보다 이해하기도, 아이디어를 생각하기도 어려웠던 문제다. 그럼에도 불구하고 내가 문제를 풀 때부터 계속 들었던 생각은 능력치 행렬은 대각선 대칭 행렬이라는 것! 이 점을 잘 이용하고 싶었는데, 풀이과정이 잘 생각나지는 않았다. 

따라서 이 문제는 아래와 같은 아이디어로 접근하면 된다. 우선 내 가장 큰 고민은 DFS의 노드로 어떤 것을 넣을까였는데, 1부터 N까지 담긴 노드를 그냥 생성하고 이들로 visited 여부를 체크해 팀을 나눈다고 생각하면 편하다. 

위 그림에서 노란색은 start 팀, 파란색은 link 팀이다. 결론은 1부터 N까지의 노드를 visited를 체크하며 N//2의 depth 만큼 내린다. 그리고 visited를 체크할 N 사이즈의 1차원리스트를 만들어 준다. 

결론적으로 visited 되지 않은 노드만, visited를 체크하며 DFS를 내리면 depth가 N//2가 되는 시점에는 visited 리스트의 방문 T/F가 위 그림처럼 N//2개, N//2개씩 동일하게 나뉘어 있을 것이다. 따라서 이를 start와 link팀으로 나뉘었다고 생각하면 된다. 그리고 matrix에서 해당하는 index를 골라 점수를 읽고, 팀별 점수의 절댓값을 계산해 min 값을 계속 업데이트 해주면 되는 문제다. 즉, 이러한 과정을 프로세스로 간단히 정리하면 다음과 같다. 

1. 각 노드의 visited를 체크할 1차원 리스트와, 1부터 N까지 DFS 노드가 존재한다고 생각
2. 각 노드를 순회할 때, unvisited 된 노드로만 DFS를 뻗으며 visited를 체크하고 depth를 늘린다. 
3. 2번의 과정을 depth가 N//2일 때까지 반복하면, visited된 노드도 정확히 N//2개가 됨을 확인한다. 
4. 3번을 확인한 후, 팀 별 점수차의 절댓값을 업데이트 한다. 

 

참고로 위 2번의 과정은 코드로 다음과 같이 구현된다. 다시 visited 여부를 False로 바꿔주는 백트래킹 과정을 잊지말자!

  for i in range(col_idx, N):
    if not visited[i]:
      visited[i] = True
      dfs(depth + 1, col_idx + 1)
      visited[i] = False            # 백트래킹

 

또한 visited 리스트로 능력치 행렬의 점수를 읽을 때, visited 리스트가 1차원 리스트이지만 능력치 행렬은 앞서 언급한 것처럼 대각에 대칭인 행렬이기 때문에 문제없이 다음과 같이 구현해 읽을 수 있다. 

  # 팀 빌딩이 완료되었을 때 
  if depth == N // 2 : 
    start, link = 0, 0

    # 각 노드를 2차원 좌표 (i, j)로 보고 각각을 순회 
    for i in range(N):
      for j in range(N):
        if visited[i] and visited[j]:
          start += mat[i][j]
        
        elif not visited[i] and not visited[j]:
          link += mat[i][j]

 

 

# Code 

위 아이디어를 코드로 구현하면 다음과 같다! 

def dfs(depth, col_idx):     # depth == raw_idx
  global result

  # 팀 빌딩이 완료되었을 때 
  if depth == N // 2 : 
    start, link = 0, 0

    # 각 노드를 2차원 좌표 (i, j)로 보고 각각을 순회 
    for i in range(N):
      for j in range(N):
        if visited[i] and visited[j]:
          start += mat[i][j]
        
        elif not visited[i] and not visited[j]:
          link += mat[i][j]

    result = min(result, abs(start-link))
    return 

  for i in range(col_idx, N):
    if not visited[i]:
      visited[i] = True
      dfs(depth + 1, col_idx + 1)
      visited[i] = False            # 백트래킹 


if __name__ == '__main__':
  N = int(input())
  mat = []                # 2차원 리스트로 능력치 행렬 적재 
  for _ in range(N):     
    mat.append(list(map(int, input().split())))

  team = [0] * N          # 인덱스 : raw / 값 : raw의 몇번째 값인지 저장 
  visited = [False] * N
  result = 99999999999    # 최솟값 저장 
  dfs(0, 0)
  print(result)

어려운 문제였다.... ㅎㅎ