2차원 배열에서 한 행, 한 열 당 숫자 하나씩을 골랐을 때 최소 합으로 만드는 방법

1. 문제

 

N*N 배열에 숫자가 들어있는데, 각 행에서 하나씩 숫자를 골라 그들의 합이 최소가 되도록 만들고 싶다.

 

그런데 세로로 같은 줄에 2개 이상의 숫자를 고를 수는 없다.

 

어떻게하면 합이 최소가 되도록 숫자를 고를 수 있을까?

 

 

2. 나의 풀이

 

어떻게 풀어야할지 도저히 모르겠더라

 

그래서 천천히 pseudo code를 생각해보았다

 

2-1)한 행에 0부터 n-1까지에서 숫자를 하나 고른다

 

2-2)고른 숫자를 더해준다

 

2-3)행수에 1을 더해서 다음 행으로 이동한다

 

2-4)이전 행에 고른 열이 아닌 다른 열에서 숫자 하나를 고른다

 

2-5)고른 숫자를 재귀적으로 반복함

 

이런식으로 생각해보고 하나하나 천천히 짜보니까 길이 좀 보이긴 하더라

 

def pick_num(x,y,sum_value):
    
    sum_value += square[y][x]

 

처음에 y행에 x열의 하나의 수를 뽑았다고 생각하고.. 합에 더해준다

 

그 다음에 y에 1을 더해서 다음 행으로 이동을 한다

 

def pick_num(x,y,sum_value):
    
    sum_value += square[y][x] #y행에서 뽑은 x열의 숫자 하나
    
    y += 1 #다음 행으로 이동

그러면 이제 행으로 순회할 이유는 전혀 없어

 

그러면 이제 x열을 0부터 n-1까지 순회해야하는데 이전에 고른 x열을 제외한 다른 열을 골라야해

 

def pick_num(x,y,sum_value):
    
    sum_value += square[y][x] #y행에서 뽑은 x열의 숫자 하나
    
    y += 1 #다음 행으로 이동
    
    for c in range(n):
        
        if x != c:
            
            pick_sum(c,y,sum_value)

 

간단하게는 위와 같이 할수 있겠지?? 이전에 뽑은 열은 x이고.. 지금 0부터 n-1까지 순회한 값이 c라고 한다면..

 

x와 c가 다를때, 그러한 수를 pick해서 재귀적으로 반복한다면??

 

근데 이렇게하면 문제가 뭘까??

 

바로 이전 행만 서로 열이 안겹치게 된다는 점이다

 

 

행이 2개이상 차이나면 거기서는 무슨 열을 골랐는지를 전혀 기억 못한다는게 문제임

 

흐름을 생각해보면 알 수 있겠지..

 

그걸 해결하는 방법이 방문 리스트를 이용하는 것이다

 

행은 0행부터 n-1행까지 순서대로 이동하면서 뽑을거니까 행이 겹칠리는 절대로 없고

 

그러면 열에 대해서만 어떤 수를 골랐는지 기억하면 된다

 

그래서 열 크기만큼 visited = [False]*n으로 초기화하고 해당 행에서, 수를 하나 뽑으면, 그 위치를 True로 바꿔주고

 

재귀적으로 넘겨준다면?

 

def pick_num(x,y,visited,sum_value):
    
    sum_value += square[y][x] #y행에서 뽑은 x열의 숫자 하나
    
    visited[x] = True #현재 x열을 골랐다고 표시를 해줌
    
    y += 1 #다음 행으로 이동
    
    for c in range(n): #해당 행에서 0부터 n-1열까지 순회를 하여
        
        if visited[c] == False #해당 열이 뽑은적이 없다면..
            
            pick_sum(c,y,visited,sum_value) #그러한 열을 뽑아서 재귀적으로 넘겨준다

 

그러면 행마다 서로 다른 열에서 수를 뽑을 수 있어

 

근데 이제 n-1행까지만 뽑을거니까.. 그리고 그럴때 뽑은 수의 합의 최솟값을 구해야하니까

 

n-1행까지 뽑아서 다 더하면, 최솟값을 갱신하면 된다

 

def pick_num(x,y,visited,sum_value):
    
    global min_sum #min_sum은 계속 갱신해나갈거니까
   
    
    sum_value += square[y][x] #y행에서 뽑은 x열의 숫자 하나
    
    visited[x] = True #현재 x열을 골랐다고 표시를 해줌
    
    y += 1 #다음 행으로 이동
    
    ##만약 y가 n이 된다면, n-1행까지 더했다는 의미이므로,
    
    if y == n:
        
        if min_sum > sum_value:
            
            min_sum = sum_value
            
    else: #y가 n-1행까지 아니라면, 수를 뽑아서 재귀적으로 더하는 작업을 수행
    
        for c in range(n): #해당 행에서 0부터 n-1열까지 순회를 하여

            if visited[c] == False #해당 열이 뽑은적이 없다면..

                pick_sum(c,y,visited,sum_value) #그러한 열을 뽑아서 재귀적으로 넘겨준다

 

모든 재귀함수에서 min_sum이 사용되어서 갱신해나가야 하니까 global 선언을 반드시 해줘야한다

 

global 선언을 하면, parameter로 사용할 필요가 없다(사용하면 에러남)

 

근데 이제 이렇게 하면 문제가 visited가 변하지 않는다는게 문제다

 

무슨말이냐면, 

 

 

위와 같은 하나의 경로를 찾았고, 여기서 수를 더했더니 2+8+2=12로 구했는데, 이제 다른 경로도 검사해봐야

 

이게 진짜 최소인지 알거잖아

 

근데 이 경로를 구하면서 visited = [True, True, True]라서, 다른 경로를 구하고자 할때,

 

이미 visited = [True, True, True]이고 이걸 그대로 가져가니까 다른 경로에서는 수를 뽑지 못한다는게 문제다

 

 

그래서 재귀경로마다 서로 다른 visited를 가져갈 수 있도록 만들어주는게 중요하다

 

def pick_num(x,y,visited,sum_value):
    
    global min_sum #min_sum은 계속 갱신해나갈거니까
   
    sum_value += square[y][x] #y행에서 뽑은 x열의 숫자 하나
    
    y += 1 #다음 행으로 이동
    
    ##만약 y가 n이 된다면, n-1행까지 더했다는 의미이므로,
    
    if y == n:
        
        if min_sum > sum_value:
            
            min_sum = sum_value
            
    else: #y가 n-1행까지 아니라면, 수를 뽑아서 재귀적으로 더하는 작업을 수행
    
        for c in range(n): #해당 행에서 0부터 n-1열까지 순회를 하여

            if visited[c] == False #해당 열이 뽑은적이 없다면..
                
                visited2 = visited[:] #새로운 방문배열 visited2를 복사하고
                
                visited2[c] = True #현재 c열을 골랐다고 표시를 해줌

                pick_sum(c,y,visited,sum_value) #그러한 열을 뽑아서 재귀적으로 넘겨준다

 

그리고 나서 재귀함수를 점검해보자

 

y행에 x열을 하나 뽑았다면, 그러한 수를 sum_value에 더해준다.

 

그리고 y+=1로 다음 행으로 이동한다

 

만약 y == n이면 n-1행까지 뽑아서 더했다는 의미니까, min값을 갱신해주고

 

그렇지 않다면 이제 현재 y행에서 0부터 n-1열까지를 순회하여

 

아직 뽑은적이 없은 visited[c] = False라면, 그러한 수 c를 뽑아서 다음 재귀함수에 넘겨준다

 

그러면 재귀적으로 위 과정이 반복될거고..

 

재귀 경로마다 서로 다른 visited를 가져가도록 만들었으니까 뭔가 잘 될것 같다

 

def pick_num(x,y,visited,sum_value):
    
    global min_sum #min_sum은 계속 갱신해나갈거니까
   
    sum_value += square[y][x] #y행에서 뽑은 x열의 숫자 하나
    
    y += 1 #다음 행으로 이동
    
    ##만약 y가 n이 된다면, n-1행까지 더했다는 의미이므로,
    
    if y == n:
        
        if min_sum > sum_value:
            
            min_sum = sum_value
            
    else: #y가 n-1행까지 아니라면, 수를 뽑아서 재귀적으로 더하는 작업을 수행
    
        for c in range(n): #해당 행에서 0부터 n-1열까지 순회를 하여

            if visited[c] == False #해당 열이 뽑은적이 없다면..
                
                visited2 = visited[:] #새로운 방문배열 visited2를 복사하고
                
                visited2[c] = True #현재 c열을 골랐다고 표시를 해줌

                pick_sum(c,y,visited,sum_value) #그러한 열을 뽑아서 재귀적으로 넘겨준다
                
T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for t in range(1, T + 1):
    # ///////////////////////////////////////////////////////////////////////////////////
    
    n = int(input())
    
    square = [list(map(int,input().split())) for _ in range(n)]
    
    min_sum = 1000 #모든 가능한 경우에서 수의 합이 절대로 1000을 넘을 수는 없다

    #현재 0행에서 0부터 n-1열까지 순회하여 하나씩 x열을 뽑아
    for x in range(n):
        
        visited = [False]*n #특히 각 열마다 서로 다른 재귀경로니까 서로 다른 visited를 가져가도록 만들어줘야
        
        visited[x] = True #현재 x열을 뽑았으니까 표시를 해주고

        pick_sum(x,0,visited,0) #만들어낸 재귀함수에 넘겨준다
    
    print('#'+str(t),min_sum,sep=' ')

 

재귀경로가 탐색하는 모습을 좀 생각해보면??

 

 

처음에 들어갈때, for문으로 0부터 n-1열까지 반복을 할거고,

 

각 반복문 수행에서 1행부터 다시 0부터 n-1열까지 순회하면서 재귀경로를 생성하고, 이게 n-1행까지 재귀적으로 탐색을 하게 설계를 했고

 

min_sum은 global변수니까 모든 경로를 탐색하면서 계속 갱신해나갈거고..

 

잘 만들었는데??

 

도저히 모르겠어서 처음에 어떤식으로 하면 좋을지 pseudo code를 생각해보고, 그것에 따라 천천히 짜보니까 잘 되네

 

근데 이렇게 하면 통과를 못해

 

#######################################################################################

모든 경우를 다 탐색하면 비효율적이거든

 

min_value가 계속 갱신해나가면서 일정하고, 만약에 하나의 경로에서 sum_value가 어느순간 min_value를 넘어간다면,

 

그것은 더 탐색할 필요도 없이 절대로 min_value가 될 수 없으므로

 

재귀경로를 끊어버려야한다. 그걸 어떻게할까? 함수를 종료하려면? 그냥 return하면 된다

 

def pick_num(x,y,visited,sum_value):
    
    global min_sum #min_sum은 계속 갱신해나갈거니까
   
    sum_value += square[y][x] #y행에서 뽑은 x열의 숫자 하나
    
    ####################백트래킹
    
    if min_value < sum_value: #현재 min_value보다 sum_value가 커진다면
        
        return  #더 볼필요도 없으므로 이러한 경로는 끊어준다
        ############################
    
    y += 1 #다음 행으로 이동
    
    ##만약 y가 n이 된다면, n-1행까지 더했다는 의미이므로,
    
    if y == n:
        
        if min_sum > sum_value:
            
            min_sum = sum_value
            
    else: #y가 n-1행까지 아니라면, 수를 뽑아서 재귀적으로 더하는 작업을 수행
    
        for c in range(n): #해당 행에서 0부터 n-1열까지 순회를 하여

            if visited[c] == False #해당 열이 뽑은적이 없다면..
                
                visited2 = visited[:] #새로운 방문배열 visited2를 복사하고
                
                visited2[c] = True #현재 c열을 골랐다고 표시를 해줌

                pick_sum(c,y,visited,sum_value) #그러한 열을 뽑아서 재귀적으로 넘겨준다

 

백트래킹으로 재귀경로를 끊어버리는 방법? 조건에 맞으면 그냥 return시키면, 해당 경로는 더 탐색하지 않고 끊긴다

 

이것도 상당히 잘 파악했다

 

 

3. 복사를 하지 않는 방법

 

만약에 visited2로 복사를 하는게 마음에 안든다면..

 

재귀함수로 들어온 수 x,y에서 x열을 뽑았으니까 현재 visited[x] = True로 표시를 하고

 

다음에 0부터 n-1열까지 순회를 하고

 

visited[c] = False이면 그 c열은 뽑지 않았으니까, 다음 재귀경로에 넘겨주면..

 

pick_sum(c,y,visited,sum_value)

 

그런 다음에 이 함수가 끝나고 나서, 다음 반복문을 수행을 할건데,

 

그 전에 visited[c] = False로 바꿔준다면?

 

for c in range(n):
    
    if visited[c] = False:
        
        pick_sum(c,y,visited,sum_value)
        
        visited[c] = False

 

위와 같이 하면.. pick_sum(c,y,visited,sum_value)가 끝나면, 그 안에서 visited[c]=True로 될건데

 

이 함수가 끝나면, 여전히 visited[c]=True로 되어 있고 for c in range(n)중이니까

 

다음 반복문 순회로 넘어갈건데 

 

그 전에 현재 뽑은 visited[c]=False로 바꿔준다면, 다른 재귀경로에서는 다른 visited를 가지고 탐색을 하겠지

 

이 정도까지 재귀함수를 이해할 수 있으면 상당히 좋다

 

상당히 잘 이해하고 파악 잘 했어

 

def pick_sum(x,y,visited,sum_value):
    
    global min_sum
    
    sum_value += square[y][x] #(x,y)좌표에서 수를 pick해서 sum_value에 더해준다
    
    ###하지 않고 완전탐색하면 시간초과

    if sum_value > min_sum: #수를 pick하면서 더하는데, 현재 min_value보다 커지면 더할필요가 없으므로 return시켜서 현재 재귀경로는 제거
        
        return
    
    #########################

    visited[x] = True #pick한 수 x좌표를 방문처리하여 다음 행에서 해당 열을 뽑지 않도록함

    y += 1 #다음 행으로 이동

    if y == n: #n-1행을 pick하고, n행이 된다면 존재하지 않으므로 지금까지 더한 sum_value와 min을 비교하여 갱신
        
        if min_sum > sum_value:
            
            min_sum = sum_value
    
    else: 

        for c in range(n): #최종 행이 아니라면, y행에서 0열부터 n-1열까지 수를 하나 pick하여 n개의 재귀경로 생성
            
            if visited[c] == False: #만약에 해당 열이 이전에 뽑지 않은 경로라면..
                
                visited2 = visited[:] #새로운 visited를 만들고..

                pick_sum(c,y,visited2,sum_value) #해당 좌표를 넣어서 수를 pick하고 더하는 재귀경로 반복


T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for t in range(1, T + 1):
    # ///////////////////////////////////////////////////////////////////////////////////
    
    n = int(input())
    
    square = [list(map(int,input().split())) for _ in range(n)]
    
    #합의 최솟값은 아무리 커도 1000을 넘지 않는다
    
    min_sum = 1000
    
    #0행의 0열부터 n-1열까지 수를 pick하여 n개의 재귀경로 생성
    
    for x in range(n):
        
        visited = [False]*n #각 경로마다 visited를 생성해줘야한다. 하나만 만들면 visited가 모든 재귀경로에서 동일하게 계속 저장되어있으니까

        pick_sum(x,0,visited,0) #수를 pick하고 더하는 과정 반복
    
    print('#'+str(t),min_sum,sep=' ')

 

4. 되돌아보기

 

행마다 하나의 수를 뽑는 방법... 잘 기억해두고

 

문제가 안풀리니까 pseudo code를 잘 생각해보고, 거기서 천천히 짜본다면 길이 보일수도 있고

 

재귀경로마다 서로 다른 visited를 가져가야하니까, 복사를 하든지, 해당 경로가 끝나고 visited를 False로 변경하고 새로운 경로에 넘겨준다든지

 

전체 재귀 경로를 탐색하면서 min값이나 max값 갱신해나가야하니까 global 변수로 선언해야하고

 

모든 재귀 경로를 탐색하지 않는 방법?? 조건에 안맞는 경로가 된다면, return시키면 그 경로는 끊어버린다