[HACKERRANK] - Crossword Puzzle

www.hackerrank.com/challenges/crossword-puzzle/problem

Crossword Puzzle | HackerRank

'-' 칸을 words로 주어진 단어들로 채우는 문제

 

<My Solution>

 

우선 채울 수 있는 칸을 먼저 찾은 후에, 해당 칸을 Recursive하게 채운다.

word의 수가 최대 10개로 제한되어있기 때문에 해당 칸에 들어갈 수 있는 단어를 모두 확인하고 대입해본다.

 

deepcopy() 함수를 사용해 완전히 새로운 배열 생성

 

from collections import deque
import copy
answer = None
def crosswordPuzzle(crossword, words):
    global answer
    size = len(crossword)
    
    for i in range(size): crossword[i] = [c for c in crossword[i]]
    words = words.split(';')
    points = deque()
    for y in range(size):
        for x in range(size):
            if crossword[y][x] == '-':
                _y, _x = y, x
                while _x+1 < size and (crossword[y][x-1]!='-' or x == 0)\
                                  and crossword[y][_x+1]=='-': 
                    _x += 1
                while _y+1 < size and (crossword[y-1][x]!='-' or y == 0)\
                                  and crossword[_y+1][x]=='-': 
                    _y += 1
                if _x != x: points.append([[y,x],[y,_x]])
                if _y != y: points.append([[y,x],[_y,x]])
    solve(crossword, points, words)
    for i in range(size): answer[i] = ''.join(answer[i])
    return answer
def solve(board, points, words):
    if len(words)==0:
        global answer
        answer = board
        return True
    point = points.popleft()
    y1,y0, x1,x0 = point[1][0],point[0][0],point[1][1],point[0][1]
    for w in words:
        _points = copy.deepcopy(points)
        _board = copy.deepcopy(board)
        _words = copy.deepcopy(words)
        if len(w)==(y1-y0+x1-x0+1):
            if x1==x0:
                for y in range(y1-y0+1): 
                    if board[y0+y][x0]==w[y] or board[y0+y][x0]=='-':
                        _board[y0+y][x0]=w[y]
                    else: break
                else:
                    _words.remove(w)
                    solve(_board,_points,_words)
            if y1==y0:
                for x in range(x1-x0+1): 
                    if board[y0][x0+x]==w[x] or board[y0][x0+x]=='-':
                        _board[y0][x0+x]=w[x]
                    else: break
                else: 
                    _words.remove(w)
                    solve(_board,_points,_words)