115. [삼성기출11]Python 백준 14889 번 스타트와 링크 자세한 설명

안녕하세요 코딩하는 덕구입니다.

백준 14889 번 스타트와 링크 입니다.

https://www.acmicpc.net/problem/14889

14889번: 스타트와 링크

 

먼저 백준 14889 번 스타트와 링크 파이썬 정답 코드입니다. 설명은 아래에 있습니다.

N = int(input())
team = [list(map(int, input().split())) for _ in range(N)]
visited = [False for _ in range(N)]
minimum = 1e9

def dfs(idx, depth):
    global minimum
    if depth == N//2:
        start, link = 0, 0
        for i in range(N):
            for j in range(N):
                if visited[i] and visited[j]:
                    start += team[i][j]
                elif not visited[i] and not visited[j]:
                    link += team[i][j]

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

    else:
        for i in range(idx, N):
            if not visited[i]:
                visited[i] = True
                dfs(i+1, depth+1)
                visited[i] = False

dfs(0, 0)
print(minimum)

 

문제 접근

모든 경우의 수를 시도해보면 됩니다.

이때 중복되는 수식은 다시 계산하지 않도록 한다면 효율적이게 해결할 수 있습니다.

dfs를 통해 구현해봅시다.

 

Python 코드 구현

사람의 개수 N,

팀의 능력치 정보 team,

방문처리를 체크할 리스트 visited,

최소값을 저장할 변수 minimum 을 초기화 합니다.

N = int(input())
team = [list(map(int, input().split())) for _ in range(N)]
visited = [False for _ in range(N)]
minimum = 1e9

 

모든 경우의 수를 체크할 함수 dfs를 구현합니다.

먼저 팀 구성이 끝났다면 (dfs의 깊이가 N//2라면) (스타트 팀은 방문한 팀, 링크 팀은 방문하지 않은 팀입니다.)

스타트와 링크의 능력치값을 초기화 합니다.

 

1. 모든 팀의 능력치 정보를 탐색하며 스타트 팀이면 (i, j가 모두 방문처리 되어있다면) start의 점수를 올려주고

2. 모든 팀의 능력치 정보를 탐색하며 링크 팀이면 (i, j가 모두 미방문이면) link의 점수를 올려줍니다.

이후 두 값을 뺀 절대값과 minumum을 비교해 값을 업데이트 합니다.

def dfs(idx, depth):
    global minimum
    if depth == N//2:
        start, link = 0, 0
        for i in range(N):
            for j in range(N):
                if visited[i] and visited[j]:
                    start += team[i][j]
                elif not visited[i] and not visited[j]:
                    link += team[i][j]

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

 

만약 팀 구성이 끝나지 않았다면 (else)

방문한 idx부터, N까지 돌면서 방문처리가 안된팀이면 

방문하고 dfs를 실행시킵니다. (이때 방문한 팀을 또 체크하지 않기 위해 i + 1을 해주고), 

모든 팀 구성이 끝나는지 확인하기 위한 dfs의 깊이 또한 + 1 해줍니다. (depth + 1)

for i in range(idx, N):
    if not visited[i]:
        visited[i] = True
        dfs(i+1, depth+1)
        visited[i] = False

 

함수를 실행시키고 출력해줍니다.

dfs(0, 0)
print(minimum)

 

파이썬 백준 14889 번 스타트와 링크 최종 코드입니다. 

N = int(input())
team = [list(map(int, input().split())) for _ in range(N)]
visited = [False for _ in range(N)]
minimum = 1e9

def dfs(idx, depth):
    global minimum
    if depth == N//2:
        start, link = 0, 0
        for i in range(N):
            for j in range(N):
                if visited[i] and visited[j]:
                    start += team[i][j]
                elif not visited[i] and not visited[j]:
                    link += team[i][j]

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

    else:
        for i in range(idx, N):
            if not visited[i]:
                visited[i] = True
                dfs(i+1, depth+1)
                visited[i] = False

dfs(0, 0)
print(minimum)

 

백준 14889 번  스타트와 링크 자세한 설명 및 Python 코드였습니다.

감사합니다.