Python/brute-force BOJ-15684 사다리조작

Posted on | In

[Python/brute-force] BOJ-15684 사다리조작

📌문제링크 풀이참고


*풀이참고 링크 들어가셔서 보시면 됩니다.

i번 세로선의 결과가 i번이 나오도록 만들기 위해 최소의 가로선을 출력하라. 단, 두 가로선이 연속하거나 접하면 안되고 가로선은 점선위에 있어야한다.

만약 정답이 3보다 크다면 -1을 출력하라.


[접근]

  1. 가로선 놓기
  2. 사다리 결과 확인
  3. 가로선 제거


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
import sys
input = sys.stdin.readline

#start 와 end가 같은지 확인하는 함수
def check(): 
    for start in range(N) :
        tmp_end = start
        for j in range(H) :  
            if board[j][tmp_end] : 
                tmp_end +=1
            elif tmp_end > 0 and board[j][tmp_end-1] :
                tmp_end -=1
        if start != tmp_end :
            return False
    return True

# 사다리 결과 확인 -> 가로선 놓기 -> 가로선 제거
def dfs(cnt,x,y):
    global ans
    if check() :
        ans = min(ans,cnt)
        return
    elif cnt >=3 : # 더이상 볼 필요없음 -1 뱉으면 됨
        return
    for i in range(x,H): # 행 탐색
        if i==x : k=y
        else : k =0
        for j in range(k,N-1): # 열 탐색
            if not board[i][j] and not board[i][j+1]:
                if j>0 and board[i][j-1] : continue # -- 인 경우
                board[i][j] = True
                dfs(cnt+1,i,j+2)
                board[i][j] = False # brute-force

                
if __name__ == '__main__' :
    N,M,H = map(int,input().split()) #N 세로 / M 가로 / H 가로선을 놓을 수 있는 위치 수
    board = [[False]*N for _ in range(H)]
    ans = 4
    if M == 0:
        print(0)
        exit(0)
    for _ in range(M):
        a,b = map(int,input().split())
        board[a-1][b-1] = True
    dfs(0,0,0)
    print(ans if ans < 4 else -1)

회고

문제 이해하기가 어려웠음ㅠ