[BOJ|PYTHON] 15684 사다리조작

• 문제정리
  https://www.acmicpc.net/problem/15684

15684번: 사다리 조작

사다리 문제.
일단 문제 파악이 쉽지 않아 여러 사다리를 마구 만들어봤다.

• 생각노트

세로선이 - - 이렇게 똑같은 높이에 그어지면 안된다.
앞에서부터 최대한으로 만족 시키다가 아무리 앞을 바꿔도 뒤에서 더이상 안되는 경우가 생긴다. 위의 경우처럼.

선을 추가하는 경우와
추가하지 않는 경우를 생각해볼 수 있는데,
선을 추가하는 경우 그 칸이 홀수일 때, 선을 추가하지 않는 경우는 그 칸이 짝수일 때이다.
선을 2개, 3개 추가할 수도 있지 않냐? 는 물음에는 대답하기 어려웠으나, (더 생각해보자)
사다리가 배치되는 칸을 기준으로 생각해보면,
무조건 1번째 칸에서 1번 세로줄이 1번으로 가는 걸 만족을 해야 , 2번째 칸으로 넘어가 탐색할 수 있고, 다시 또 2번째 세로줄이 2번으로 가는 걸 만족을 시켜야 한다 이렇게 .. 끝까지 탐색해볼 수 있다.

• 구현방법 선택

1. 일단 모든 경우의 수를 찾는 완전탐색-> combination으로 그냥 쫙 다 돌리고싶다.. 0개를 사용해서 해보고? 1개를 사용해서 해보고? ... N개를 사용해서 해보기 의 방식을 생각해볼 수 있다.

2. 이 문제는 위에 볼 수 있는 '안 됨을 인지한 순간 더 이상 가지 않고 다시 전 단계에서 다른 경우를 찾는다'는 것에서
N-Queens문제와 동일,  백트래킹으로 구현해볼 수 있겠다. (백트래킹 : DFS를 동반한 가지치기 방식)
이 때 너무 감사하게도 3개 이상이 되면 그냥 -1로 출력하라고 했으므로 가지치기 조건이 매우 감사하게 주어졌다!
-->2번방식으로 고

• 코드화

기본적인 백트래킹 코드는 다음과 같다. 재귀 + 가지치기
dfs(x) + check
dfs(x)에서 check함수를 통과(return True)하게 되면 dfs(x+1 - 다음 단계를 의미)로 간다

import sys
input=sys.stdin.readline
N,M,H=map(int,input().split())
Board=[[0 for _ in range(N)] for _ in range(H)] #row(열)이 H, col(행)이 N
for _ in range(M):
    g,s=map(int,input().split())
    Board[g-1][s-1]=1 #그어진 곳을 표시한다.


def check(board):# 현재 board 상태에서 어떤 col에서 나아가도 제자리로 오는지 확인
    for i in range(N): #모든 col에서 확인할 것이다.
        row=0; col=i; #일단 출발은 row가 0일 때부터.
        while row<H:
            #해당 row의 col과 col-1을 살펴보면서 내려간다.
            if col<N and board[row][col]==1:
                col+=1;
            elif col>0 and board[row][col-1]==1:
                col-=1;
            row+=1;
            if col==N+1: return False
        if col!=i: return False
    return True


def dfs(board, res,column):
    global ans
    if check(board): #만약 어디에서든 제자리로 돌아온다는 것이 확인된다면
        if res<=3: ans=min(ans,res); 
        return
    else: #아직 제자리로 돌아오지 못한다.
        if res<3: #res가 3이 넘으면 굳이 가지 않는다.
            for row in range(H):
                for col in range(column,N):
                    if not board[row][col]:
                        if (col==0 and not board[row][col+1]) or (col==N-1 and not board[row][col-1]) or (0<col and col<N-1 and not board[row][col-1] and not board[row][col+1]):
                                board[row][col]=1
                                dfs(board, res+1, col)
                                board[row][col]=0

ans=4
dfs(Board, 0,0) #0번
if ans>3: print(-1)
else:
    print(ans)

'''
시간초과 해결 - dfs 인자에 column 넣기
'''

• 주의해야할 것들

Backtracking 가지치기 유형을 빨리 눈치채기?? --> 제한 3이 큰 힌트
가장 쉽게 설명할 수 있는 문제가 이 문제랑, N-Queens 문제다.

안 됨을 인지한 순간 더 이상 가지 않고 다시 전 단계에서 다른 경우를 찾는다.
구현 방법은 Dfs + Check 함수로 하는 경우가 많은데
dfs에서 check(T/F 반환)로 판단 후 가능하면 dfs(다음단계로) 가는 로직이다.

9%에서 시간초과 -> visited 함수 뿐만 아니라 DFS 파라미터로 column과 관련한 정보를 추가로 주어 시간초과를 해결할 수 있다.(마치 visited 배열처럼 한 번 방문한 행은 방문하지 않는다)

• 더 생각하기

이 문제를 맨 처음 고려할 때 DP도 떠오르면서 DP와 백트래킹+DFS 의 차이에 대해 혼자 심오한 고민이 시작되었다(??)
DP가 작은 문제를 풀기 위해서 Top Down 방식으로 재귀함수를 호출하며 안될 때 더이상 호출하지 않는 방식이
DFS+백트래킹의 원리와 비슷해보였기 때문.
이 둘의 차이를 좀 더 생각해봐야 겠다.

비효율적으로 갔던 곳을 또 방문하지 않도록 하는 방법에 대해 더 생각하기(재귀함수 parameter, visited 배열, flag 등의 수단이 있을 수 있겠다.)