[Python] 백준 15684 - 사다리 조작

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

15684번: 사다리 조작

알고리즘 유형: 백트래킹 + dfs

 

풀이: 만만히(?) 봤는데, 생각 보다 엄~~청 꼬여서 애먹었다.

처음에는 추가된 가로선의 배열을 깊은복사로 일일히 복사해주었고, 시간 초과가 발생했다..

그 뒤 방향을 잘못잡아 연달아 실수를 했고, 결국에 백트래킹 + dfs로 문제를 풀었다.

백트래킹 기법을 사용해 추가된 가로선의 배열을 true -> false로 복구 해주어 간단히 풀 수 있었다.

가로선 추가가 max 4개 이니 백트래킹과 dfs로 접근이 가능했던 것이다.

 

다음은 상세한 주석 + 코드이다.

 

# https://www.acmicpc.net/problem/15684
#
import sys
input = sys.stdin.readline

n,m,h = map(int, input().split())
answer = -1
graph = [[False] * (n+1) for _ in range(h+1)]

# 사다리 타기
# 1번 세로부터 시작
def go(graph):
    for i in range (1,n+1):
        # 현재 세로선
        curLine = i
        # 현재 점선 -> 초기화 1
        curDotLine = 1
        while curDotLine <= h:
            # 사다리가 오른쪽 으로
            if graph[curDotLine][curLine]:
                curLine +=1
            # 사다리가 왼쪽으로 
            elif graph[curDotLine][curLine-1]:
                curLine -=1
            curDotLine +=1
        # 하나라도 세로선이 종착선과 다르면 return False    
        if curLine != i: 
            return False
    # 모두 통과 -> return True        
    return True
    
# 가로선 추가에 대한 dfs
def dfs(x, y, cnt):
	# 더이상 추가될 가로선이 없다 -> 사다리타기 go
    if cnt == 0:
        return go(graph)
    for i in range(x, h+1):
        for j in range(y,n+1):
            # 가로선 추가가 가능 and "연달아 있는 가로선"이 없음.
            if graph[i][j] == False and j <n and graph[i][j-1] == False and graph[i][j+1] == False:
                graph[i][j] = True
                # 가능 -> return True
                if dfs(i,j,cnt-1):
                    return True
                graph[i][j] = False
        y = 0

for _ in range(m):
    a,b = map(int, input().split())
    graph[a][b] = True

# 가로선을 0개 부터 3개 까지 추가한다.
for i in range(4):
	# 이전 가로선 추가로 해결이 안됨 -> 새 dfs
    if(answer == -1): 
        if dfs(1, 1, i):
            answer = i
            break
print(answer)