[python] 15684번 사다리 조작

1. 문제 링크 및 문제

https://www.acmicpc.net/problem/15684

1-1 문제 요약

:N*M 크기의 맵, 가로선을 추가하여 i번 세로선의 결과가 i번으로 나와야 함.
이 때 추가해야 하는 가로선 개수의 최솟값(최대 3개)

2. 해결 방법 생각해보자 ...

1. i번 세로선의 결과가 i번으로 나오는 코드 작성 T/F
2. False 일 때 사다리(가로선) 1개 추가 생성
   조건. 가로선이 연속하지 않게 작성
3. 가로선 추가한 맵으로 1, 2 반복.
   가로선이 3개일 때도 1번이 F 이면 -1

3. 코드 (해결방법순 코드 작성)

0. arr에 사다리 생성하기

N,M,H = map(int, input().split())
arr = [[0]*N for _ in range(H)]

for _ in range(M):
    x,y = map(int, input().split())
    arr[x-1][y-1] = 1

1. check 함수 작성 (i번 세로선 결과 i번 )

• idx = i번 세로선
• now = i번 세로선이 사다리에 의해 이동된 수
  -> 오른쪽으로 갈 경우 now + 1 ,왼쪽으로 갈 경우 now -1
• H의 높이만큼 움직였을 때 (도착했을 때 )
  -> idx = now, 출발세로선 = 이동된 세로선 확인

def Check():
    for idx in range(N):
        now = idx
        for x in range(H):
            if arr[x][now] == 1 : #오른쪽이 1
                now += 1
            elif now>0 and arr[x][now-1] == 1 : #왼쪽이 1
                now -= 1
        if idx != now : 
            return False
    return True

2. check가 False 일 때 사다리(가로선) 1개 추가 생성

3. 리턴 조건

• 조건
  -> 1. i번 세로선이 i번으로 나올 때

ans=4
ans =  min( 생성된 사다리 수 , ans )

-> 2. 최솟값보다 사다리 많이 생성됐을 때

return : if ans <= cnt : return

-> 3. 사다리가 3개이상 생성됐을 때

if cnt == 3 : return

• 조건 전체 코드

ans = 4

def dfs(cnt,x,y) :
    print(cnt,x,y)
    global ans
    if ans <= cnt : return
    if Check():
        ans = min(ans,cnt)
        return
    if cnt == 3 : return

4. 전체 코드

N,M,H = map(int, input().split())
arr = [[0]*N for _ in range(H)]

for _ in range(M):
    x,y = map(int, input().split())
    arr[x-1][y-1] = 1

def Check():
    for idx in range(N):
        now = idx
        for x in range(H):
            if arr[x][now] == 1 : #오른쪽이 1
                now += 1
            elif now>0 and arr[x][now-1] == 1 : #왼쪽이 1
                now -= 1
        if idx != now : 
            return False
    return True
    
ans = 4

def dfs(cnt,x,y) :
    print(cnt,x,y)
    global ans
    if ans <= cnt : return
    if Check():
        ans = min(ans,cnt)
        return
    if cnt == 3 : return

    for i in range(x,H):
        k=y if i==x else 0
        for j in range(k, N-1):
            if arr[i][j] : 
                j+=1
            else :
                arr[i][j] = 1
                dfs(cnt+1, i,j+2)
                arr[i][j] = 0

dfs(0,0,0)
print(ans if ans<4 else -1)

참고

https://ryu-e.tistory.com/69