[백준 14552번] 파이썬 - Mahjong

http://www.acmicpc.net/problem/14552

14552번: Mahjong

 

 

# 조건

• 마작을 연습하기 위해 프로그램을 만든다.
• 136개의 패를 가지고 하는 게임이지만 우리는 단순화 시켜서 삭수패 9종류 (1~9삭)를 4개씩, 총 36개의 패만 가지고 만든다.
• 머리는 같은 패 2개의 조합을 말하고, 몸통은 연속된 패 3개 혹은 같은 패 3개의 조합을 말한다.
  • (2삭): 패가 하나이므로, 머리도 몸통도 될 수 없다.
  • (3삭, 3삭): 같은 패 2개가 있으므로, 이 두 패의 조합은 머리이다.
  • (7삭, 8삭, 9삭): 7, 8, 9는 연속된 수 이므로, 이 세 패의 조합은 몸통이다.
  • (1삭, 3삭, 5삭): 1, 3, 5는 연속된 수가 아니다. (서로 1씩 차이가 나야한다.) 그러므로, 이 세 패의 조합은 몸통이 아니다.
  • (8삭, 9삭, 1삭): 9삭과 1삭은 연속된 수가 아니다 (둥글게 이을 수 없다.)
  • (9삭, 9삭, 9삭): 같은 패 3개가 있으므로, 이 세 패의 조합은 몸통이다.
  • (4삭, 5삭, 4삭): 4, 4, 5는 연속된 세 수가 아니다. 그러므로, 이 세 패의 조합은 몸통이 아니다.
  • (8삭, 8삭, 8삭, 8삭): 패가 4개 이므로, 머리도 몸통도 될 수 없다.
• 36개의 패 중 적당히 14개를 모아서, 머리 1개와 몸통 4개 혹은 머리 7개의 조합으로 만들려고 한다.
• 각 패는 반드시 하나의 머리나 하나의 몸통에 속해야 한다. 이를 패가 완성되었다고 한다.
• 단, 머리 7개를 모을 때, 같은 종류의 머리가 2개 있으면 안된다.
• 패 13개가 있을 때, 적당한 한 개의 패를 더 가져와서, 패를 14개로 만들어 완성시키려고 한다.
• 자기가 13개의 패가 있고, 남은 23개 중 어떤 패를 한 개 가져 왔을 때, 그 패가 완성될 수 있다면, 그것을 대기패라고 한다.
• 대기패가 없다면 -1을 출력

 

# 접근 방법 및 Solution

• 현재 가지고 있는 패 13개를 기록해준다.
• 이후 머리 7개가 되는 대기패가 있는지 확인해준다.
  • 1차원 리스트이기 때문에 리스트 슬라이싱을 통해 복사해주어도 deepcopy
  • 1~9번 카드를 하나씩 넣어주며 개수가 2개라면 +1을 해준다.
  • 7머리가 아니라면 chkpae 함수 들어가준다.
• check_card(카드 리스트, 머리 수, 몸통 수, 카드번호)
  • 낮은 숫자부터 확인하며 패를 가지고 있다면
  • 이 때, 3장 이상이고 몸통이 4가 안된다면 몽통으로 넣고 되는지 확인해준다.
  • 2장 이상이고 머리가 없으면 머리로 넣고 확인해준다.
  • 연속된 세 숫자가 있으면 몸통에 넣고 확인해준다.
  • 모두 안된다면 남는 패가 있으므로 불가능 선언
• 처음 1 1 1 1과 같이 4개인 경우 머리도 몸통도 될 수 없다는 조건을 빼먹고 생각하여 구현이 힘들었다.

import sys  
sys.stdin = open('input.txt')  
  
# 대기패 추가된 카드 리스트, 머리 수, 몸통 수, 현재 카드번호 인자로 받기  
def check_card(card_2, head, body, num):  
    # 머리 1 몸통 4 완성이라면 return  
    if head == 1 and body == 4:  
        return True  
    # 패 복사해주기  
    card_3 = card_2[:]  
    # 1부터 시작  
    while num < 10:  
        # 패 가지고 있다면 확인 시작  
        if card_3[num] > 0:  
            # 가지고 있는 카드 3개이고 몸통이 4개가 안된다면 몸통으로 넣고 확인  
            if card_3[num] == 3 and body < 4:  
                card_3[num] -= 3  
                flag = check_card(card_3, head, body+1, num)  
                # 된다면 바로 종료  
                if flag:  
                    return True  
                # 안되면 원상복구  
                card_3[num] += 3  
  
            # 가지고 있는 카드 2개이상이고 머리가 없다면 머리로 넣고 확인  
            if card_3[num] >= 2 and not head:  
                card_3[num] -= 2  
                flag = check_card(card_3, head+1, body, num)  
                if flag:  
                    return True  
                card_3[num] += 2  
  
            # 연속된 세 숫자 있으면 몸통에 넣고 확인  
            if num < 8 and card_3[num+1] and card_3[num+2]:  
                card_3[num] -= 1  
                card_3[num+1] -=1  
                card_3[num+2] -=1  
                flag = check_card(card_3, head, body+1, num)  
                if flag:  
                    return True  
  
            # 위 조건 모두 안된다면 남는패가 있으므로 불가능 선언  
            return False  
        else:  
            num += 1  
  
  
#카드 받아 준 후 기록해주기  
info = [*map(int, input().split())]  
card = [0] * 10  
  
for i in info:  
    card[i] += 1  
  
# 머리 7개 되는 경우 확인  
result = []  
  
# 4장이 이미 사용되었다면 넘어간다.  
for i in range(1,10):  
    if card[i] == 4:  
        continue  
    # 대기패 돌아가며 추가해줄 리스트  
    card_2 = card[:]  
    card_2[i] += 1  
    head_7 = 0  
  
    # 대기패 하나씩 넣어주며 2개라면 +1 해준다  
    for j in range(1, 10):  
        if card_2[j] == 2:  
            head_7 += 1  
    # 머리 7개가 된다면 결과에 넣어주고 다음 패 확인  
    if head_7 == 7:  
        result.append(i)  
    # 아니라면 몸통 4, 머리 1의 경우가 되는지 확인  
    elif check_card(card_2,0,0,1):  
        result.append(i)  
if result:  
    print(*result)  
else:  
    print(-1)