삼성SDS_백준_실버2_스타트와 링크 (브루트포스_combinations_그래프 없는 DFS)

RostoryT·2022년 10월 7일
0

Corporation_Coding Test

목록 보기
13/19




메모

N명의 사람 (짝수)

각 팀은 반 쪼개서 N/2명씩 구성 -> 스타트팀 링크팀

S_ij : i번사람과 j번 사람이 만났을 때 얻는 에너지

팀의 능력치 = sum(S_ij들)

  • 주의사항 : S_ij와 S_ji는 다를 수도 있다

    • i는 j랑 케미가 10이라고 생각하는데, j는 i랑 케미가 4라고 생각할수도ㅋ
  • 중요 : i랑 j가 같은 팀에 속했을 때 얻는 에너지는 S_ij + S_ji

    • 1,3,6이 팀이 되었으면
      • (S13 + S31) + (S16 + S61) + (S36 + S63)
  • 해야할것 : 스타트팀 능력치 <-> 링크팀 능력치 차이 최소화


알고리즘 및 방법

  • 힌트보고 생각난건데
  • 걍 이거안되나
  • combinations를 쓰는데
    • (전체) C (len(n)/2) 해서 나온거 sum vs 그 나머지 절반 sum 비교
    • 이때 1차원 벡터의 인덱스로만 체크하는거
1. 리스트의 인덱스를 가져온다
s = [i for i in range(len(S))]

2. 두 팀으로 나누기 때문에 n/2 만큼만 추출할거
for star in combinations(s, len(s)/2)
    3. star에는 인덱스 넘버들이 있으니 나머지 계산해서 link팀 추출
    link = s - star
    
    4. star팀 모든 경우의수 계산 => ij ji 더해줌
    for a in combinations(star, 2)
        aa += S[a[0]][a[1]] + S[a[1]][a[0]]
        
    5. link팀 모든 경우의수 계산 => ij ji 더해줌
    for b in combinations(link, 2)
        bb += S[b[0]][b[1]] + S[b[1]][b[0]]
        
    6. min값 추출 => 기존 vs star와 link 차이
    ans = min(ans, abs(aa-bb))

솔루션 코드 - 내가 푼

from itertools import combinations
import sys
input = sys.stdin.readline

leng = int(input())
S = [list(map(int, input().split())) for _ in range(leng)]
#S = [[0, 1, 2, 3], [4, 0, 5, 6], [7, 1, 0, 2], [3, 4, 5, 0]]
#S = [[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]]
#S = [[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]]

ans = 999999
s = [i for i in range(len(S))]

for star in combinations(s, int(len(s)/2)):
    aa = 0
    bb = 0
    # start에는 인덱스 넘버들이 있음
    link = list(set(s) - set(star))
    
    for a in list(combinations(list(star), 2)):
        aa += S[a[0]][a[1]] + S[a[1]][a[0]]
        
    for b in combinations(list(link), 2):
        bb += S[b[0]][b[1]] + S[b[1]][b[0]]
        
    ans = min(ans, abs(aa-bb))

print(ans)



솔루션 코드 - 블로그

  • DFS 방식 (중요)

    • 최근에 DFS문제중에 이런 패턴이 많이 보임 (파이썬 책에서 리트코드 문제 풀던거)
    • 일단 그래프가 주어지지 않았고
    • 계산과정 자체가 브루트포스 느낌인데
    • 모든 과정을 다 봐야하는 경우를 DFS로 풀어냈음. 그리고
      • visited[i] = True
      • dfs(depth + 1, i + 1)
      • visited[i] = False
    • 이런식으로 치고빠지더라
  • 코드 출처 : https://ji-gwang.tistory.com/260

    • if depth가 n//2일 때, 다음과 같이 비교
    • 이렇게 하는 이유는 ij를 역으로만 바꿔서 ji만 더해주면 되기 때문(약간의 최적화)
import sys

input = sys.stdin.readline

N = int(input())
array = []
result = 1e9                                         #결과값 출력을 위한 result값을 문제의 범위를 벗어나는 큰 수로 초기화
visited = [False] * (N + 1)                         #방문여부를 확인하는 리스트
for _ in range(N):
    array.append(list(map(int, input().split())))


def solve(depth, idx):
    global result
    if depth == (N // 2):                                  # N // 2 번만큼 재귀를 돌면
        start, link = 0, 0                                  #start팀과 link팀 0으로 선언
        for i in range(N): 
            for j in range(i + 1, N):                      #이중 리스트의 열은 굳이 0부터 돌필요가 없기 때문에 i + 1 로 범위를 좁혀준다. 
                if visited[i] and visited[j]:              #만약 i,j 둘다 방문 했다면 
                    start += (array[i][j] + array[j][i])   #방문한 사람을 스타트팀에 더해준다.
                elif not visited[i] and not visited[j]:   # 방문 안한 i j 는 링크팀이므로
                    link += (array[i][j] + array[j][i])    #방문안한 사람을 링크팀에 더해준다
        
        result = min(result, abs(start - link))            #최솟값을 결과값에 대입
    for i in range(idx, N): 
        if not visited[i]:                                 #만약 방문을 안했다면
            visited[i] = True                              #방문으로 처리
            solve(depth + 1, i + 1)                        #재귀를 돈다 
            visited[i] = False                             #방문 완료 처리


solve(0, 0)
print(result)

profile
Do My Best

0개의 댓글