백준[1721] 상자퍼즐(파이썬)

구현 + 완전탐색 문제이다. 구현이 조금 까다로워서 골드4 수준인듯 하다.

나는 조건문 + 재귀문을 이용해서 완전 탐색을 구현했다.

코드가 조금 지저분 하긴 한데 더 효율적인 방법이 있으면 소개부탁드린다.

import sys
input = sys.stdin.readline
data = []
n = int(input())
nn = n ** 2

for _ in range(nn):
    line = list(map(int, input().split()))
    data.append(line)

from collections import deque

def calc(d, count):
    q = deque(d)
    for _ in range(count):
        x = q.pop()
        q.appendleft(x)
    return list(q)

answer = [[0] * n for _ in range(n)]

answer_top = [[[0] * 5 for _ in range(n)] for _ in range(n)]
visited = [0] * nn
dx = [0, 1, -1, 0]
dy = [1, 0, 0, -1]

from copy import deepcopy

def func(pos_x, pos_y):
    global data, visited, answer, answer_top, n, nn
    
    #만약 끝까지 탐색이 끝났다면 결과 출력하고 종료
    if pos_x >= n or pos_y >= n:
        for h in range(n):
            for w in range(n):
                print(answer_top[h][w][0], end = ' ')
            print()
        for h in range(n):
            for w in range(n):
                print(answer[h][w], end = ' ')
            print()
        exit()
        return
    
    #입력으로 받은 모든 상자퍼즐들을 확인한다
    for i in range(nn):
		#만약 이미 사용한 상자라면 건너뛴다.
        if visited[i] == 1:
            continue

        #일단 가장자리인지 확인하고 가장자리 값이 0이 아니라면 건너뛴다.
        for j in range(4):
            cube = calc(deepcopy(data[i][1:]), j)
            if pos_x == 0:
                if cube[0] != 0:
                    continue
            if pos_y == 0:
                if cube[3] != 0:
                    continue
            if pos_x == n-1:
                if cube[2] != 0:
                    continue
            if pos_y == n-1:
                if cube[1] != 0:
                    continue
			#가장자리 값이 모두 0이라면 이제 인접면의 수를 체크한다.
            check = False
            for e in range(4):
                nx = pos_x + dx[e]
                ny = pos_y + dy[e]
                if 0 <= nx < n and 0 <= ny < n:
                	#인접면의 값이 존재한다면 내가 현재 두려고 하는 상자와의 값이 일치한지 확인
                   	#만약 일치하지 않는다면 check = True하고 break
                    if answer_top[nx][ny][0] != 0:
                        if e == 0:
                            if answer_top[nx][ny][4] != cube[1]:
                                check = True
                                break
                        if e == 1:
                            if answer_top[nx][ny][1] != cube[2]:
                                check = True
                                break
                        if e == 2:
                            if answer_top[nx][ny][3] != cube[0]:
                                check = True
                                break
                        if e == 3:
                            if answer_top[nx][ny][2] != cube[3]:
                                check = True
                                break
            #모두 일치한다면 해당 좌표에 상자를 위치시키고 다음 좌표로 넘어간다.
            if not check:
                visited[i] = 1
                answer_top[pos_x][pos_y] = [data[i][0]] + cube
                answer[pos_x][pos_y] = j

                if pos_y == n-1:
                    func(pos_x + 1, 0)
                elif pos_y < n-1:
                    func(pos_x, pos_y + 1)
                #만약 최종 결과를 찾을 수 없다면 초기화하고 다음 상자가 올 수 있도록 준비
                answer_top[pos_x][pos_y] = [0] * 5
                answer[pos_x][pos_y] = 0
                visited[i] = 0

func(0, 0)