[Python] 백준/BOJ 2784번: 가로 세로 퍼즐 (Silver 2)

💻 Problem

문제 보러 가기

 

아래와 같은 가로 세로 퍼즐을 풀어보자.

6개의 단어가 주어졌을 때, 이를 가지고 가로 세로 퍼즐을 만드는 프로그램을 작성하시오. 단어 3개는 가로줄, 3개는 세로줄로 배치해야 한다.

6개의 줄에 알파벳 대문자로 이루어진 단어가 주어진다. 이 단어는 사전순으로 정렬되어 있다.

 

✏️ Solution 1

내가 처음 풀이한 방법은 아래와 같다.

1. 6개의 단어 중 3개를 뽑는다. (가로 단어로 사용)
   • 순서가 있으므로 순열이다.
2. 가로 단어로 퍼즐을 만들어서 세로 단어를 추출한다.
3. 추출한 세로 단어 조합과 (1)에서 뽑히지 않은 단어 조합이 같다면 퍼즐이 완성된다.

이거 풀면서 고민을 많이 했다.. 머리 아팠음 ㅠ

선택되지 않은 단어들이 가로 단어에서 뽑은 세로 단어들과 같은지 비교를 어떻게 할까 싶었다.

선택되지 않은 단어들을 다시 순열 돌려야 하나.. 했는데 생각해 보니 두 리스트를 정렬해서 비교하면 되는 거였다!

import sys
input = sys.stdin.readline

def check_puzzle():
    remain = []
    vertical = []

    # 선택되지 않은 단어 찾기 (세로 단어)
    for i in range(6):
        if not selected[i]:
            remain.append(voca[i])
    
    # 가로 단어에서 세로 단어 추출하기
    for i in range(3):
        vertical.append(horizontal[0][i] + horizontal[1][i] + horizontal[2][i])

    # 선택되지 않은 단어들이 가로 단어에서 뽑은 세로 단어들과 같다면 퍼즐 완성
    if sorted(remain) == sorted(vertical):
        print(*horizontal, sep='\n')
        exit()

def permutation(select_idx):
    # 1. 기저 조건
    # 모든 원소를 선택함
    if select_idx == 3:
        check_puzzle()
        return
    
    # 2. 전처리 로직
    # 아직 다 선택하지 않음
    for i in range(6):
        # 이미 선택한 원소는 패스
        if selected[i]:
            continue
        
        selected[i] = True
        horizontal[select_idx] = voca[i]

        # 3. 재귀 호출
        permutation(select_idx + 1)

        # 4. 후처리 로직
        # 사용 다 했으면 되돌리기
        selected[i] = False

voca = [input().rstrip() for _ in range(6)]
selected = [False] * 6
horizontal = [''] * 3

permutation(0)
print(0)

 

✏️ Solution 2

처음에는 itertools 모듈의 순열 함수를 사용하려고 했는데, 이렇게 하면 뽑힌 단어들만 알고 뽑히지 않은 단어들을 알 수 없어서 직접 순열을 구현했다. (Solution 1 방식)

 

하지만 다른 사람의 풀이를 보니 itertools 모듈의 순열 함수를 사용해도 가능한 방법이 있었다.

딕셔너리를 활용하면 되는 것이었다..!

 

1. 6개의 단어들 중 3개의 단어(가로 단어)를 순열로 뽑는다.
2. 입력받은 6개의 단어 개수를 센 딕셔너리를 만든다.
3. 뽑은 가로 단어 3개를 하나씩 살펴본다.
   1. 딕셔너리에서 가로 단어를 하나 제거한다.
   2. 가로 단어에서 세로 단어를 추출한다.
   3. 추출한 세로 단어를 딕셔너리에서 제외한다.

import sys
from collections import Counter
from itertools import permutations
input = sys.stdin.readline

def check_puzzle():
    for d in dic.values():
        if d != 0:
            return
        
    # 단어들의 value가 모두 0이면 퍼즐 완성
    print(*element, sep='\n')
    exit()

voca = [input().rstrip() for _ in range(6)]

for element in permutations(voca, 3):
    dic = Counter(voca)

    for i in range(3):
        # 가로 단어 제거
        dic[element[i]] -= 1
        # 가로 단어에서 세로 단어 추출
        vertical = element[0][i] + element[1][i] + element[2][i]
        # 세로 단어 제거
        dic[vertical] -= 1

        check_puzzle()

print(0)

 

✏️ Solution 3

처음에 Solution 1대로 풀다가 마지막쯤에 3개를 뽑을 게 아니라 그냥 6개를 나열하면 되겠다는 생각이 들긴 했다..

3개를 뽑으면 뽑지 않은 단어가 뭔지 찾아야 하는데.. 그냥 ₆P₆을 하면 앞에 3개는 가로 단어, 뒤에 3개는 세로 단어 하면 되는데..

근데 거의 다 풀었을 때 생각난 거라서 그냥 이어서 풀었었다.. ㅋㅋㅋㅋ

 

그래서 그 방법으로 풀어봤다!

이번에 파이썬에 all이라는 함수를 처음 알게 됐다. (왜 이제 알았지???? 좋은데????)

all()은 인자의 모든 것이 참이면 true, 하나라도 거짓이 존재하면 false를 반환하는 함수이다.

 

horizontal[j][i] == vertical[i][j]라는 조건문을 통해 가로 단어와 세로 단어를 비교했다.

여기서 하나라도 false가 걸린다면 all()이 false를 반환할 테고, 퍼즐은 완성되지 않는다.

all()이 참이면 퍼즐이 완성된 것이다.

import sys
from itertools import permutations
input = sys.stdin.readline

voca = [input().rstrip() for _ in range(6)]

for p in permutations(voca):
    horizontal = p[:3]
    vertical = p[3:]

    if all(horizontal[j][i] == vertical[i][j] for i in range(3) for j in range(3)):
        print(*p[:3], sep='\n')
        exit()

print(0)