[백준/2784] 가로 세로 퍼즐 (Python)

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

2784번: 가로 세로 퍼즐

 

Difficulty : Silver 2

 

Status : Solved

 

Time : 00:14:48

 

---

 

문제 설명

 

 

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

가로줄

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개의 단어를 생각하면 된다.

 

입력 예시

 

ANA
ANA
DAR
DAR
RAD
RAD

 

출력 예시

 

DAR
ANA
RAD

 

 

---

 

풀이

 

여섯 개 중 가로로 배치할 단어 세 개를 고르는 경우의 수 : C(6, 3) = 20 

단어 셋을 나열하는 경우의 수 : P(3, 3) = 3! = 6

 

이므로 총 120가지의 경우만을 테스트해보면 된다. 당연히 브루트포스.

가로세로 비교를 쉽게 하기 위해 transpose를 정의했는데, 다른 더 효율적인 해법도 당연히 존재하므로 얼마든지 다른 방법을 시도해보는것도 좋다고 생각한다.

 

 

풀이 코드

from itertools import combinations, permutations

word_list = [input().strip() for _ in range(6)]

def transpose(lst) :
  result = ['']*3 
  for i in range(3) :
    for j in range(3) :
      result[j] += lst[i][j] 
  return result
      
answer = 'zzzzzzzzz'
for num_list in combinations(range(6), 3) :
  other_nums = set(range(6)) - set(num_list)
  words = [ word_list[i] for i in num_list ]
  other_words = list( word_list[i] for i in other_nums )
  other_words.sort()

  for orders in permutations(range(3), 3) :
    t_words = [ words[i] for i in orders ]
    target_words = transpose(t_words)
    target_words.sort()
    if target_words == other_words :
      t_words = ''.join(t_words)
      if answer > t_words :
        answer = t_words

if answer != 'zzzzzzzzz' :
  for i in range(3) :
    print(answer[i*3:i*3+3])
else :
  print(0)

풀이 완료!