[백준 2784번] : 가로 세로 퍼즐 파이썬 풀이

가로 세로 퍼즐 

1 초

128 MB

1197

488

403

43.757%

문제

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

가로줄

1. device used to cool a PC
2. solid water
3. to obtain

세로줄

1. small, soft, sweet fruit
2. strong playing card
3. fisherman's tool

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

입력

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

출력

6개 단어를 3*3 가로 세로 퍼즐에 놓을 수 없다면 0을 출력한다. 그렇지 않다면, 3개 줄에 퍼즐을 출력한다. 만약 가능한 답이 여러개라면 사전순으로 앞서는 것을 출력한다. 사전순으로 비교를 할 때는, 모두 한 줄로 이어붙인 9개의 단어를 생각하면 된다.

예제 입력 1 

ANA
ANA
DAR
DAR
RAD
RAD

예제 출력 1 

DAR
ANA
RAD

예제 입력 2 

EVO
HEP
HIR
IVA
PAD
ROD

예제 출력 2 

HEP
IVA
ROD

예제 입력 3 

AKO
CES
DOC
DON
ESI
KES

예제 출력 3 

0

 

표의 크기가 3x3밖에 되질 않으므로 브루트포스 알고리즘을 통해 접근하였다.

 

주어진 단어들은 총 6개이므로 6개중에 3개를 뽑아서 가로로 배치한 후 완성된 표의 가로 3개 단어와 세로 3개 단어가 모두 입력값에 있는지 확인한다.

 

가능한 답이 여러개인 경우, 사전순으로 가장 앞서는 것을 출력하는 것이 문제의 조건인데 이미 주어진 입력값은 사전순으로 입력받는다는 것을 보장받았으므로 새로 정렬할 필요없이 앞에서부터 3개를 뽑는 과정을 끝까지 수행하면 된다.

 

단어 3개를 뽑는 과정을 위해 반복문,재귀함수,백트래킹을 사용하여 단어를 한개씩 뽑다가 3개를 뽑았을때 검증하는 방식으로 구현하였다.

위 알고리즘을 적용한 코드는 아래와 같다.

 

import sys
words = [] # 입력받은 단어들(가로,세로 상관 무관)
for _ in range(6):
    words.append(input())

selected_words = []
# 앞에서부터 3개씩 뽑는 함수
def select_word(depth): # depth는 현재까지 몇개의 수를 뽑았는지
    global selected_words
    if depth == 3: # 3개의 수를 뽑았으면 조건을 만족하는지 확인 후 종료
        check()
        return # 재귀 종료
    for i in range(len(words)):
        selected_words.append(words[i])
        select_word(depth+1)
        selected_words.pop()
    

# 모든 단어를 다 포함하는지 체크
def check():
    # print("#########")
    # print(selected_words)

    # 가로줄과 세로줄에서 만들어진 문자들을 모두 저장 후 정렬
    check_array = []
    for i in range(3):
        check_array.append(selected_words[i])
    
    for i in range(3):
        word = ''
        for j in range(3):
            word += selected_words[j][i]
        check_array.append(word)

    check_array.sort()
    # 얻은 문자열 조합과 기존에 갖고 있는 문자열이 일치한다면 모든 단어를 다 포함한 것임
    if check_array == words:
        for word in selected_words:
            print(word)
        sys.exit(0)

select_word(0)
print(0)

 

https://www.acmicpc.net/problem/2784

2784번: 가로 세로 퍼즐