백준 2784 : 가로 세로 퍼즐

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

2784번: 가로 세로 퍼즐

https://github.com/HPYoo/swcodingtest/commit/754ea8d3b3d10a2749c1a09859cb5e3be895ee06

sw coding 2784 update(Baekjoon) · HPYoo/swcodingtest@754ea8d

1. 문제 이해

문제에 대한 예제를 한 번 풀어보면,

 

F	A	N
I	C	E
G	E	T

이렇게 된다.

이와 같이 주어진 단어들을 이용해 모든 줄에서 한 번씩 단어가 언급되면 풀 수 있는 문제이다.

본 문제에서는 주어진 단어를 3개씩 조합해 배열에 넣어두고 하나씩 체크하는 식으로 문제를 풀었다.

이 때, 순열 함수를 이용했는데 itertools 를 사용하지 않고 연습해볼겸 직접 작성했다.

def permutation(arr, t):
    result = []
    if t == 0 :
        return [[]]
    for i in range(len(arr)):
        elem = arr[i]
        rest_arr = arr[:i] + arr[i + 1:]
        for P in permutation(rest_arr, t - 1) :
            result += [[elem] + P]
    return result

해당 문제에서는 배열의 크기가 정해져있기 때문에 메모리 초과문제, 시간 초과 문제에 걸릴 일이 없어서 사용했다.

 

2. 전체 코드

메모리 : 114328 KB, 시간 : 124 ms, 풀이시간 : 50분

문제가 무슨 소린가 갑자기 이해를 잘 못해서 오래걸림

words = []
for i in range(6) :
    temp = input()
    words.append(temp)

def permutation(arr, t):
    result = []
    if t == 0 :
        return [[]]
    for i in range(len(arr)):
        elem = arr[i]
        rest_arr = arr[:i] + arr[i + 1:]
        for P in permutation(rest_arr, t - 1) :
            result += [[elem] + P]
    return result

permut = permutation(words, 3)

def solve():
    answer_board = []
    while permut :
        x, y, z = permut[0]
        del permut[0]
        board = [x, y, z]
        # 행 기준으로 words 제거
        temp = words.copy()
        cnt = 6
        check = True
        for i in range(3):
            if board[i] in temp :
                temp[temp.index(board[i])] = True
                cnt -= 1
            else :
                check = False
        if check :
            for i in range(3):
                char = board[0][i] + board[1][i] + board[2][i]
                if char in temp :
                    temp[temp.index(char)] = True
                    cnt -= 1
                else :
                    check = False
        if check and cnt == 0 and temp.count(True) == 6:
            answer_board.append([board[0] + board[1] + board[2]])
    return answer_board

result = solve()
result.sort()

if not result :
    print(0)
else :
    for i in range(0, 9, 3):
        print(result[0][0][i] + result[0][0][i+1] + result[0][0][i+2])