백준 20444 색종이와 가위

링크 : https://www.acmicpc.net/problem/2661

문제

아이디어 : N-Queen이랑 비슷해보인다

입력 길이만 주고 → 결과를 리턴

제한조건(동일한 숫자가 연속해서 나타나면 x ) 를 보고 → 백트래킹해서 가지치면서 진행해야겠다

까지생각했음

DFS를 써야겠다

BFS로 하면 안될거라고 생각했던게, 애초에 백트래킹할때 DFS로밖에 못한것도있고, 메모리제한이 128메가라서 1, 2, 3 순서대로 재귀 진행하면, 길이가 n 인상태에서 리턴되는 제일빠른 숫자가 정답 이라고 생각했다

망한코드

import sys 
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
N = int(input().strip())

words = ['1', '2', '3']
def dfs(x) :
    global x 

    #종료조건
    if len(x) == N :
        print("here is x " + str(x))
        return x 

    #덧셈조건 
    for word in words : 
        temp = x + word 

        i = 1
        while i<= len(temp)//2 :
            if temp[-2*i:-i] == temp[-i:] :
                print(temp, temp[-2*i:-i] , temp[-i:])
                return   
            i+=1
        dfs(temp)


start = ""
print(dfs(""))

DFS를 잘못써서 개같이 멸망

1인 상태에서는 ‘11’, ‘12’, ‘13’, 을 확인해야하고, ‘11’은 연속된 숫자이기때문에 1 → 11 → 12 로 확인해야하는데
실제로 해보니 1→ 11 → 2로 움직여서, 이부분을 못해결해서 답지를 봤다

정답코드

def back_tracking(idx):

    #1
    for i in range(1,(idx//2) +1):
        if s[-i:] == s[-2 * i:-i]: return -1
    #2
    if idx == n:
        for i in range(n):
            print(s[i], end='')
        return 0

    #3
    for i in range(1, 4):
        s.append(i)
        if back_tracking(idx + 1) == 0:
            return 0
        s.pop()

if __name__ == "__main__":
    n = int(input())
    s = []
    back_tracking(0)

#1에서는 재귀조건(연속된 숫자가 나오는지 를 확인하고)

#2에서는 길이(idx) 가 n 일때 진행하는 종료조건을 확인하는거고

#3에서는 for i in [1,2,3]으로 하나씩 넣어가면서 백트래킹을 진행한다.
리스트s 는 ‘현재 백트래킹중인 숫자가 담겨져있는 리스트’ 이다.

if back_tracking(idx+1) == 0 : 만약 한칸이 늘어났는데, 0이 리턴됐다라는것은
실제로 0이 리턴되는구간은 #2의 리턴값밖에 없기때문에, 이는 ‘어쨋든 길이가 끝까지 갔구나' 라는것을 의미한다.
그게 아니라면, 리턴값이 -1이라서 #3에서 pop() 한다음 다른값이 들어가는 방식으로 구현됐다