[알고리즘 문제] 단백질 사냥꾼 (Python / 파이썬)

문제

자신의 몸이 허약하다고 생각한 정택은 강해지기위해 운동을 하기 시작했다. 알고리즘 피트니스 센터의 센터장인 종민의 조언에 따라 “먹는 것 까지 운동이다.” 라는 철칙을 잘 따르고 있다. 전날 무리하게 운동한 여파로 늦잠을 자게되어, 오늘 먹을 단백질 도시락을 챙길 여유가 없었다. 어제 무리하게 운동한 것이 아까운 정택은 사무실 근처에 있는 편의점을 돌며 얻을 수 있는 최대의 단백질을 확보하려고 한다. 같은 단백질 함양을 가진 제품은 동일한 제품이고, 같은 도시락을 여러 번 먹으면 질리기때문에 서로 다른 제품을 통해 단백질을 섭취하고자 한다. 힘이 상승하고자하는 정택은 편의점을 ‘+’ 모양으로 순회하려고 한다.

위와 같이 편의점 정보가 존재한다고 했을 때, 각 칸에 해당하는 숫자는 해당 편의점에서 얻을 수 있는 단백질의 g 수 이다. 첫 번째 그림에서 얻을 수 있는 서로 다른 종류의 단백질 도시락 개수는 4개이며, 얻을 수 있는 단백질 g 수는 7+2+10+9 로 28 이다. 두 번째 그림에서 얻을 수 있는 서로 다른 종류의 단백질 도시락 개수는 5개이며, 얻을 수 있는 단백질 g 수는 1+3+4+9+10 로 27 이다.
순회 경로의 경우 만약 중앙을 기점으로 봤을 때, 상하좌우 경로의 길이를 서로 달리할 수 있다. 이때 경로의 길이 최솟값은 상하좌우 각각 모두 1로 고정한다. 즉, 하나의 편의점만 들를 수 없고, 직선 형태, 'ㄱ', 'ㄴ' 등의 모양으로 순회를 할 수 없다는 것이다. 예를 들면, 다음과 같이 다양하게 존재할 수 있다.

시작 지점에서 출발하여 다시 시작 지점으로 돌아온다고 했을 때, N * N 의 편의점 단백질 도시락 정보에서 가장 많이 얻을 수 있는 단백질 함량의 합을 구해보자.
편의점 정보가 주어졌을 때, 답을 구하는 과정은 다음과 같다. (총 6가지가 존재하는 것은 아니며, 몇 가지 경우는 생략되었다.)

마지막 그림에서 얻어지는 숫자의 합 1+2+3+5+6+7+8 인 32 가 정답이다.

입력

첫 번째 줄에 테스트 케이스의 개수 T(5 ≤ T ≤ 50) 가 주어진다. 각 테스트 케이스의 첫째 줄에 N(3 ≤ N ≤ 20) 이 주어지고, N 개의 줄에 걸쳐 N 개의 숫자가 공백을 통해 구분하여 입력된다. 각각의 입력되는 숫자는 1 부터 100 을 포함한 정수이다.

출력

각 테스트 케이스에 해당하는 결과값을 한 줄에 하나씩 “#t result” 포맷으로 출력한다. (t는 1부터 T까지의 정수이다)

---

문제 풀이 

문제가 다소 길고 복잡해보이지만 문제 해결을 위한

아이디어만 떠올리면 쉽게 해결할 수 있는 문제이다. 

 

문제에 제시된 조건은

1. 무조건 + 모양으로 탐색해야 하며 

2. 숫자가 같은 것은 같은 도시락으로 간주하고 한번만 더한다. 

3. 이렇게 더한 값들 중 최대값을 구해야 한다. 

 

이 조건을 어떻게 해결할지 잘 생각해보면 

1. 테두리에 있는 원소들은 절대로 + 모양을 만들 수 없다. 

그 외의 원소들은 무조건 + 모양을 만들 수 있다. 

따라서 테두리에 있는 원소들을 제외하고 탐색하면 된다.

2. + 모양 내에 존재하는 수 중 같은 수가 여러개 있더라도 한번씩만 더해야 한다.

따라서 별도의 배열을 만들어 배열에 이미 추가시킨 원소라면 추가시키지 않는다.

3. 최대값을 구한다는 것은 최대한 원소를 많이 더해야 한다는 것이다. 

따라서 만들 수 있는 + 모양 중 제일 큰 모양에 (상하좌우 모든 방향으로 범위의 끝까지)

존재하는 원소들을 모두 더해주면 최대값이다.  

 

이 아이디어에 따라 테두리를 제외한 모든 원소들마다 만들 수 있는 가장 큰 + 모양에서

(상하좌우 방향으로 범위의 끝까지) 한번씩만 수들을 배열에 넣어 

배열에 존재하는 합을 구하고 그 중 최대값을 출력하면 답이 된다. 

---

My Code

# + 모양에 포함된 원소들의 합을 구해주는 함수
def get_max(x, y):
    temp = []
    # x, y 위치로부터 상하좌우 방향으로 범위의 끝까지 탐색
    for i in range(n):
        if array[x][i] not in temp: # 좌우로 탐색하며 배열에 포함되지 않은 원소라면 삽입
            temp.append(array[x][i])
        if array[i][y] not in temp: # 상하로 탐색하며 배열에 포함되지 않은 원소라면 삽입
            temp.append(array[i][y])
    return sum(temp) # 배열에 포함된 원소들의 합을 구해 반환

for tc in range(int(input())):
    n = int(input()) # 편의점 크기 

    array = []
    for _ in range(n):
        array.append(list(map(int,input().split()))) # 편의점 정보

    max_value = 0
    for i in range(n):
        for j in range(n):
            if i == 0 or i == n - 1 or j == 0 or j == n - 1: # 테두리 원소들은 넘어감
                continue 
            max_value = max(max_value, get_max(i, j)) # 구한 합들 중 가장 큰 값 찾아줌

    print('#' + str(tc + 1), end = ' ')
    print(max_value)