백준 4658(삼각형 게임) - 해결

삼각형 게임

 

문제

삼각형 게임은 시작할때 여섯개의삼각형을 부여받는데, 각 변에는 숫자가 쓰여있다(그림 참고). 이 삼각형들을 돌리고 움직여서 육각형을 만들어야 하는데, 반드시같은 숫자가 쓰여있는 변끼리만 닿아 있어야 한다. 삼각형을 뒤집을 순 없다. 완성된 육각형은 다음과 같다.

점수를 계산하는 기준은 육각형의 각 변에 쓰인 숫자들의 합이다.

당신은 어떤 삼각형 세트를 부여받았을때 그 세트에서 나올 수 있는 최고점수를 계산하는 것이다.

 

입력

입력은 여러개의 세트로 이루어져 있다.

각 세트는 1이상 100이하의 정수 세개로 이루어진 수열 6개로 이루어져 있다.

수열 안의 수는 삼각형 변에 쓰여 있는 수를 시계방향으로 왼쪽부터 입력한 것이다.

세트는 별표(*) 하나를 포함하고 있는 줄로 구분된다.

마지막 세트는 달러($)기호로 종결한다.

 

출력

각 세트 순서에 맞추어, 육각형 형성이 가능하다면 육각형의 최고점수를, 불가능하다면 none을 출력한다.

---

처음에는 어떻게 풀지 막막했다.

이어지는걸 어떻게 판단해야할지 구하지 못했다.

그러다가 생각한 방법이 총 나오는 방법이 크게 3가지라고 생각을 하여 처음 삼각형의 1, 2, 3번 숫자를 선택하였을 때 이어지는 숫자가 있는가 확인하는 방법이다.

그리고 다른 삼각형에 같은 숫자가 있다면 다음 숫자는 더하는 숫자가 될것이고 그다음 숫자는 다음 이어지는 숫자가 될 것이다. 이러한 방법을 생각하여 문제를 풀었다.

import sys

input = sys.stdin.readline

def dfs(n,now,sum_v):
    global total
    
    # 6개의 삼각형을 다 탐색했으면 
    if n == 6:
        # 마지막 삼각형과 첫번째 삼각형이 
        # 이어지는지 확인
        if tris[0][cnt] == now:
            total = sum_v
        else:
            total = 0
        return
    
    # 6개의 삼각형 탐색
    for i in range(6):
        if visit[i] == 1:
            continue
        # 3개의 숫자 확인
        for j in range(3):
            # 이어지는가 확인
            if now == tris[i][j]:
                visit[i] = 1
                # 다음의 숫자는 더하고
                # 다다음 숫자와 이어지는 삼각형을 찾기위해 전달
                dfs(n+1,tris[i][(j+2)%3],sum_v+tris[i][(j+1)%3])
                visit[i] = 0

while 1:
    tris = []
    for _ in range(6):
        tris.append(list(map(int,input().split())))
    max_v = 0
    
    visit = [0] * 6
    
    # 3개의 숫자중 하나씩 선택
    for cnt in range(3):
        total = 0
        dfs(0,tris[0][cnt],0)
        if max_v < total:
            max_v = total
            
    # max_v 가 0 이면 어떤 방법으로도
    # 못만드다는 것이기 때문에 none
    if max_v:
        print(max_v)
    else:
        print('none')
    
    # 다음 입력
    next = input().strip()
    if next == "*":
        pass
    elif next == "$":
        break