[DFS/BFS/완전탐색] 14889번 - 스타트와 링크(DFS, 완전탐색, 백트래킹)

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

(한줄평) 아이디어를 떠올리고 구현하는 것은 어렵지 않았으나 시간단축을 위한 방법을 고민해봐야했던 문제!

1 ~ N 번호를 가진 사람들이 있을 때 두 팀으로 나누었을 때 각 팀의 능력치(팀에 속한 모든 쌍의 능력치의 합)의 차이의 최솟값을 구하는 문제였다. 두 팀으로 나눌 수 있는 모든 경우의 수를 따져봐야하는 완전 탐색(백트래킹)문제로 DFS를 이용하여 풀 수 있다. 물론 조합을 구할 때 combinations 라이브러리를 사용할 수도 있다. 여기서 풀이 1, 2 둘다 DFS를 이용하여 구현했고 설계방식에 조금 차이가 있는데 풀이2가 메모리, 시간 측면에서 더 효율적이므로 풀이2를 추천한다.

(풀이1) 내 풀이

풀이 시간: 30분 이내

1) 문제 해결 아이디어

이 방식은 1, 3번 처럼 팀 A, B의 구성원을 리스트로 만들고 그 리스트 정보로부터 능력치를 계산한다는 점이다.

 

<동작과정>

1. A, B팀의 구성원을 담을 리스트(teamA, temaB)를 각각 생성한다.

2. DFS를 이용하여 n명 중에서 절반(n/2)을 골라 A팀(teamA)에 배정한다. (조합)

3. 팀 배정이 모두 완료되면 A팀이 아닌 번호는 B팀(teamB)에 배정한다.

4. A, B팀의 능력치(powerA, powerB) 계산하기

5. 두 팀의 능력치 차이(diff)와 최솟값(min_diff)를 비교해 최솟값 갱신

 

2) 소스코드

import sys
input = sys.stdin.readline

# DFS
# n명에서 절반 뽑기
def dfs(depth, start):
  global min_diff
  # 절반 뽑았으면
  if depth == n / 2:
    powerA, powerB, diff = 0, 0, 0 
    tempB = []	# B팀 구성원
    # B팀 구성하기
    for i in range(1, n + 1):
      # teamA가 없으면
      if i not in tempA:
        tempB.append(i)
    # A, B팀 능력치 합 구하기
    for i in range(n):
      for j in range(n):
        # 둘 다 속해있으면
        if i + 1 in tempA and j + 1 in tempA:  powerA += graph[i][j]
        elif i + 1 in tempB and j + 1 in tempB:  powerB += graph[i][j]
    diff = abs(powerA - powerB)    # 능력치 차이 계산
    min_diff = min(min_diff, diff)
    cnt += 1  # 경우의 수 1개 증가
    return

  # 팀 선택하기(조합)
  for i in range(start, n + 1):
    tempA.append(i)
    dfs(depth + 1, i + 1)
    tempA.pop()
          
n = int(input())  # 사람수(짝수)
# 능력치 정보(n * n)
graph = [list(map(int, input().split())) for _ in range(n)]
min_diff = 1e9  # 능력치 차이 최솟값
tempA = []  # A팀 구성원

dfs(0, 1)
print(min_diff)

(풀이2) 다른 풀이를 참고한 시간 단축 코드(추천)

풀이 시간: 30분 이내

1) 문제 해결 아이디어

풀이1과 가장 다른 점은 굳이 구성원 번호를 담는 리스트를 생성하지 않고 길이가 n인 리스트(temp)를 선언하여 구성원들이 A팀에 배치됬으면 0으로 B팀에 배치됬으면 1로 설정하게 하는 것이다.

사실상 초기에 값을 0으로 셋팅해놓았으므로 DFS로 B팀에 배치될 번호의 값을 1로 바꿔주고 DFS를 호출하고나서는 0으로 원상복귀 시켜주면 된다.

 

<동작과정>

1. n명의 팀 정보(A팀→0, B팀→1)를 담는 리스트(temp) 생성한다. 

(여기서 값을 모두 0으로 초기화하여 초기에는 A팀에 모두 배정된 것으로 가정한다.)

2. DFS를 이용하여 n명 중에서 절반(n/2)을 골라 B팀(teamA)에 배정한다. (조합)

3. 팀 배정이 모두 완료되면 A, B팀의 능력치(powerA, powerB) 계산하기

5. 두 팀의 능력치 차이(diff)와 최솟값(min_diff)를 비교해 최솟값 갱신

 

2) 소스코드

import sys
input = sys.stdin.readline

# DFS
# n명에서 절반 뽑기
def dfs(depth, start):
  global min_diff
  # 절반 뽑았으면
  if depth == n / 2:
    powerA, powerB, diff = 0, 0, 0 
    # A, B팀 능력치 합 구하기
    for i in range(n):
      for j in range(n):
        # 둘다 A팀이면
        if temp[i] == 0 and temp[j] == 0:  powerA += graph[i][j]
        # 둘다 B팀이면
        elif temp[i] == 1 and temp[j] == 1:  powerB += graph[i][j]
    diff = abs(powerA - powerB)    # 능력치 차이 계산
    min_diff = min(min_diff, diff)
    return

  # 팀 선택하기(조합)
  for i in range(start, n):
    temp[i] = 1  # B팀 선택
    dfs(depth + 1, i + 1)
    temp[i] = 0  # 원상복귀
          
n = int(input())  # 사람수(짝수)
# 능력치 정보(n * n)
graph = [list(map(int, input().split())) for _ in range(n)]
min_diff = 1e9  # 능력치 차이 최솟값
# (A팀: 0, B팀: 1)
temp = [0 for _ in range(n)]

dfs(0, 0)
print(min_diff)