[백준] 링크와 스타트

출처:: www.acmicpc.net/problem/15661

분류:: 브루트 포스 

 

1. 문제 이해 및 해결과정

- 딱 같은 수 만큼 링크팀과 스타트팀이 선택하는 것이 아니라, 최소1개 ~ N-1개까지 각각 팀선택이 가능하다 -> 어떻게 구현하지? dfs -> 선택하거나 안하거나 모든 경우의 수를 구하자

 

2. 풀이방법

 1. [ python ] dfs

#링크와 스타트
#https://www.acmicpc.net/problem/15661
import sys
sys.setrecursionlimit(10**6)
sys.stdin = open("input.txt","r")
n=int(input())
board=[list(map(int,input().split())) for _ in range(n)]
team = [False] * (n + 1) #팀의 선택여부 
minv=1e9
def dfs(t,d): #선택된 팀의 개수, 트리의 깊이
    global minv
    if d==n:#트리의 깊이는 n=4라면 d==n일때 stop , 끝까지 모든 팀을 본 것이므로
        return
    if t> (int(n//2)+1): #스타트팀과 링크 팀의 차이를 작게하는것이므로, 어느것이 스타트팀인지, 링크팀인지가 중요하지 않다.
        #n의 반정도를 선택하면 나머지것은 자동으로 선택되므로, 1,5의 차이 5,1의 차이는 같아서
        return
    if t>=1: #팀이 하나이상 선택되었다면
        start=link=0
        for i in range(n):
            for j in range(n):
                if team[i]==True and team[j]==True: #2번 3번 팀이 선택된 것이라면,board[2][3]+board[3][2]
                    start+=board[i][j]
                elif team[i]==False and team[j]==False:# 0번 1번이 남았으면, board[0][1]+board[1][0]
                    link+=board[i][j]
        minv=min(abs(start-link),minv)
        print(team)
    #여기서 else: 를 쓰면 안된다. 팀이 하나이상 선택되었든 아니든, 일단 경우의 수를 모두 찾아야 한다.
    team[d]=True
    dfs(t+1,d+1) #팀을 선택한 경우
    team[d]=False
    dfs(t,d+1) #팀을 선택하지 않은 경우
dfs(0,0)
print(minv)

2. [ python ] 

#링크와 스타트
#https://www.acmicpc.net/problem/15661
import sys
n=int(input())
board=[list(map(int,input().split())) for _ in range(n)]
minv=1e9
def dfs(t,d,k):
    global minv
    if d==n:
        return
    if t==k:
        start=link=0
        for i in range(n):
            for j in range(n):
                if team[i]==True and team[j]==True:
                    start+=board[i][j]
                elif team[i]==False and team[j]==False:
                    link+=board[i][j]
        minv=min(abs(start-link),minv)
    else:
        team[d]=True
        dfs(t+1,d+1,k)
        team[d]=False
        dfs(t,d+1,k)
for k in range(1,int(n//2)+2): #주의할 부분 
    team = [False] * (n + 1)
    dfs(0,0,k)
print(minv)

 

3. 오답원인

 

  1. dfs에서 else문 , if t>=1 의 else 문은 t가 0일때만 가능한 조합의 수를 모두 체크하게 된다. n//2범위까지 모든 경우의 수를 체크해야한다

  2. for k in range(1,int(n//2)+2) : 처음에는 int(n//2)+1 이라고 했었는데 1~int(n//2)+1 까지 탐색해야한다고 생각했기 때문이다. 하지만 파이썬에서는 , -1범위까지 탐색하므로 숫자를 하나 더 크게 해야한다. 

 

4. 알게된 점