[백준 15684번] 사다리 조작 - python

문제 링크

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

15684번: 사다리 조작

 

풀이 

두번째 푸는건데 ㅠㅠ 또 다른 블로그를 참고 하게 되는,, 세번째는 꼭 푼다. 

 

백트래킹 문제이다. 

헷갈리는 점은 H는 행, 모든 세로선(N)이 열이라는 것이다. 

graph[H][N] 에 사다리를 표시한다.

 

1. graph[i][j] = 1 이란, 

세로선 j 에서 j+1 사이에  가로 i번째에 가로선을 놓았다는 것이다. 

 

2. dfs을 통해 가로선을 놓고, i에서 i로 가는 것이 가능한지 check() 함수로 확인한다.

1) dfs

- check()를 통해 가능하다면, 가로선을 놓은 횟수인 cnt를 갱신하고 return 

- cnt 가 현재 최솟값인 ans보다 크거나 같거나, 3이라면 불가능하다는 것이므로 return

- 현재 세로선부터 확인한다.

현재 위치와 같은 가로선이라면, 현재 세로선부터 확인하고 

다른 가로선이라는 0번째 세로선부터 확인한다.

만약, 현재 위치에 가로선을 못놓거나, 왼쪽에도 가로선이 존재한다면, continue 

가로선을 놓을 수 있다면, 가로선을 놓고 dfs 실행한다.

이 때 dfs를 실행할 때 다음 가로선 위치가 아니라 다다음 가로선을 전달하는데, 가로선은 연속하여 놓을 수 없기 때문이다. 

 

2) check

세로선 기준으로 위에서부터 아래로 내려오면서

현재 위치(오른쪽으로 연결된 가로선)나, 왼쪽에 가로선이 있다면 세로선을 그 위치로 이동시킨다. 

다 이동하고 마지막 세로선이 현재 세로선과 다르다면 실패이므로 False 리턴 

 

# i -> i 가능한지 확인 
def check():
    for i in range(n):
        col = i
        for j in range(h):
            if graph[j][col] :
                col += 1
            elif col >0 and graph[j][col-1]:
                col -=1
        if col !=i :
            return False

    return True

# 가로선 놓기 
def dfs(cnt, x,y ):
    global ans

	# 가능하다면 놓은 가로선 수 갱신 
    if check():
        ans = min(ans,cnt)
        return
	# 현재 최솟값보다 크거나, 3 이상이면 실패 
    if cnt >= ans or cnt == 3 :
        return

    for i in range(x, h):
        # 같은 행이면 y 부터 확인
        if i == x:
            k = y
        # 다른 행이면 0부터 확인
        else :
            k = 0
		
        # 가로선 놓을 수 있는 위치인지 확인하고 놓기 
        for j in range(k, n-1):
            if graph[i][j] or graph[i][j+1]:
                continue
            if j > 0 and graph[i][j-1]:
                continue
            # 가로줄 만듬
            graph[i][j] = 1
            # 연속된 가로줄 만들지 않기 위해 j+2 호출
            dfs(cnt+1, i ,j + 2)
            graph[i][j] = 0

n,m,h = map(int,input().split())

graph = [ [0] * n for _ in range(h)]
ans = 4
for _ in range(m):
    a, b = map(int,input().split())
    graph[a-1][b-1] = 1

dfs(0, 0 ,0)

if ans < 4 :
    print(ans)
else :
    print(-1)