백트래킹

백준 14888

 

import sys

inputN = int(sys.stdin.readline())

N = list(map(int,sys.stdin.readline().split()))

M = list(map(int,sys.stdin.readline().split()))

plus = M[0]

minus = M[1]

multiple = M[2]

divide = M[3]

minnum = int(1e9)

maxnum = -int(1e9)

def DFS(plus,minus,multiple,divide,sum,depth) :

    global minnum

    global maxnum

    if depth == inputN :

        minnum = min(minnum,sum)

        maxnum = max(maxnum,sum)

        return

    if plus>0 :

        DFS(plus-1,minus,multiple,divide,sum+N[depth],depth+1)

   

    if minus >0 :

        DFS(plus,minus-1,multiple,divide,sum-N[depth],depth+1)

   

    if multiple>0 :

        DFS(plus,minus,multiple-1,divide,sum*N[depth],depth+1)

    if divide >0:

        DFS(plus,minus,multiple,divide-1,int(sum/N[depth]),depth+1)

DFS(plus,minus,multiple,divide,N[0], 1)

print(maxnum)

print(minnum)

 

plus를 하나씩 줄이고, N의 array를 처음부터 하나씩 계속 추가하는 형식으로 계산하여, 
그 계산 과정의 숫자를 기록하여 재귀 호출하는 형태로 구현하였다. 

 

*기억해야 할 것은, 이전 상태를 끌고 와야될 배열이든,숫자든,depth이든 계산하는 것이 중요하다.

 

종이에 tree의 동작구조를 그린것이 크게 도움이 되었지만 , 매개변수의 전달을 생각하지 못했다. 

매개변수에는, 이전 상태를 끌고 올 것을 대입하는 것을 기억하자. 

 

백준 14889 

import sys

sys.setrecursionlimit(100000)

N = int(sys.stdin.readline())

graph = [[] for _ in range(N+1)]

forloop =0

for i in range(1,N+1) :

    graph[i]= [0] + list(map(int,sys.stdin.readline().split()))

print(graph)

visited = [False] * (N+1)

minsum = int(10000000)

def DFS(totalarr,asum,index):

    global minsum

    if len(totalarr) == (N/2) :

        bteam = []

        bsum = 0

        for i in range(len(visited)):

            if visited[i] == False :

                bteam.append(i)

       

        for i in range(1,len(bteam)):

            for j in range(i,len(bteam)) :

                bsum = bsum+graph[i][j]+graph[j][i]

        if abs(asum-bsum) < minsum :

               

            minsum = abs(asum-bsum)

            return

   

    for i in range(1,N+1) :

        if visited[i] == False :

            visited[i] = True

            DFS(totalarr+[i],(asum+graph[index][i]+graph[i][index]),i)

            visited[i] = False

   

visited[1] = True

DFS([1],0,1)

print(minsum)

 

 

* 자꾸 array에 [0]을 추가하지 않아 정사각형이 아닌 인접 리스트를 만든다거나, 

혹은 graph[i] = 이 아니라 graph[i]+로 작성하는 등 실수를 한다. 해당 실수를 정말 주의하자 .

 

예제 case는 대부분 잘 동작하나, 동작하지 않는 경우가 존재했다. 어떤 실수를 했을지를 고민해 봐야겠다. 

 

+시간 초과까지 발생했다. 이렇게 되면 완전히 틀렸다는 의미 .. 

 

import sys

N = int(sys.stdin.readline())

graph = [[] for _ in range(N+1)]

for i in range(1,N+1) :

    graph[i]= [0] + list(map(int,sys.stdin.readline().split()))

visited = [False] * (N+1)

minsum = int(10000000)

def DFS(number,index):

    global minsum

    if number == (N/2) :

        asum = 0

        bsum = 0

        for i in range(1,N+1):

            for j in range(i,N+1) :

                if visited[i] == True and visited[j] == True:

                    asum = asum + graph[i][j] + graph[j][i]

                elif visited[i] == False and visited[j] == False :

                    bsum = bsum+ graph[i][j] + graph[j][i]

        minsum = min(minsum,abs(asum-bsum))

        return

    for i in range(1,N+1) :

        if visited[i] == False :

            visited[i] = True

            DFS(number+1,i)

            visited[i] = False

   

visited[1] = True

DFS(1,1)

print(minsum)

 

bsum만 마지막에 계산하는게 아니라, 종단의 조건시 asum도 계산하게 변경한 코드 

값은 모두 맞으나, 문제는 시간초과가 발생한다. 

 

import sys

sys.setrecursionlimit(100000000)

N = int(sys.stdin.readline())

graph = [[] for _ in range(N+1)]

for i in range(1,N+1) :

    graph[i]= [0] + list(map(int,sys.stdin.readline().split()))

visited = [False] * (N+1)

minsum = int(10000000)

def DFS(number,index):

    global minsum

    if number == (N/2) :

        asum = 0

        bsum = 0

        for i in range(1,N+1):

            for j in range(i+1,N+1) :

                if visited[i] == True and visited[j] == True:

                    asum = asum + graph[i][j] + graph[j][i]

                elif visited[i] == False and visited[j] == False :

                    bsum = bsum+ graph[i][j] + graph[j][i]

        minsum = min(minsum,abs(asum-bsum))

        return

    for i in range(index,N+1) :

        if visited[i] == False :

            visited[i] = True

            DFS(number+1,i)

            visited[i] = False

   

visited[1] = True

DFS(1,1)

print(minsum)

 

접근 자체는 유려하게 잘 진행하였으나, 아직까진 과정 등이 약간 미숙한 점이 있다. 조금 더 자주 풀어, 이러한 것들이 손에 익게끔 노력하자.