[python] BOJ 백준 15684: 사다리조작

1. 문제  

다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖는다. 아래 그림은 N = 5, H = 6 인 경우의 그림이고, 가로선은 없다.

초록선은 세로선을 나타내고, 초록선과 점선이 교차하는 점은 가로선을 놓을 수 있는 점이다. 가로선은 인접한 두 세로선을 연결해야 한다. 단, 두 가로선이 연속하거나 서로 접하면 안 된다. 또, 가로선은 점선 위에 있어야 한다.

사다리에 가로선을 추가해서, 사다리 게임의 결과를 조작하려고 한다. 이때, i번 세로선의 결과가 i번이 나와야 한다. 그렇게 하기 위해서 추가해야 하는 가로선 개수의 최솟값을 구하는 프로그램을 작성하시오.

2. 입력   

첫째 줄에 세로선의 개수 N, 가로선의 개수 M, 세로선마다 가로선을 놓을 수 있는 위치의 개수 H가 주어진다. (2 ≤ N ≤ 10, 1 ≤ H ≤ 30, 0 ≤ M ≤ (N-1)×H)

둘째 줄부터 M개의 줄에는 가로선의 정보가 한 줄에 하나씩 주어진다.

가로선의 정보는 두 정수 a과 b로 나타낸다. (1 ≤ a ≤ H, 1 ≤ b ≤ N-1) b번 세로선과 b+1번 세로선을 a번 점선 위치에서 연결했다는 의미이다.

가장 위에 있는 점선의 번호는 1번이고, 아래로 내려갈 때마다 1이 증가한다. 세로선은 가장 왼쪽에 있는 것의 번호가 1번이고, 오른쪽으로 갈 때마다 1이 증가한다.

입력으로 주어지는 가로선이 서로 연속하는 경우는 없다.

3. 출력   

i번 세로선의 결과가 i번이 나오도록 사다리 게임을 조작하려면, 추가해야 하는 가로선 개수의 최솟값을 출력한다. 만약, 정답이 3보다 큰 값이면 -1을 출력한다. 또, 불가능한 경우에도 -1을 출력한다.

4. 해결방법   

이 문제는 DFS를 이용한 구현문제이다. 가로선과 세로선을 탐색하면서 사다리를 놓을 수 있는 곳에 먼저 놓고, 계속해서 재귀적으로 사다리를 놓을 수 있는 곳에 놓다가, 만약 문제에 제시한 조건과 어긋나게 된다면 백트래킹하여 이전 버전에서 또 탐색하게 되는 것이다. 문제에서는 백트래킹 조건으로 3개 보다 더 많이 사다리를 놓는 것으로 설정을 해주었다. 또한 이미 구한 최소값보다도 더 넘어가게 되면 탐색을 종료시켜 효율성을 증가시킬 수 있다. 

1) check 함수: i번째 세로줄이 i번째로 돌아오게 되는지 판단하는 함수이다. 모든 세로줄을 탐색하면서 만약에 가로선이 오른쪽에 존재한다면 현재 있는 위치를 1 증가시켜주고, 가로선이 왼쪽에 존재한다면 현재있는 위치를 1 감소시켜준다. 그렇게 해서 끝까지 진행을 하였을때 시작위치와 다르다면 조건을 만족하지 않으므로 False를 리턴하고 그렇지 않으면 True를 리턴한다. 

2) dfs 함수: 현재 몇개의 사다리를 놓았는지와 현재 탐색중인 좌표를 매개변수로 받는다. 만약 사다리를 놓은 개수가 3개를 초과하는 경우이거나 이미 구한 최소값을 넘어가는 경우에는 리턴하여 백트래킹할 수 있게 해준다.  그게 아니라면 지금 탐색중인 행부터 차례대로 탐색한다. 단, 지금 탐색중인 행일 경우에는 탐색하던 열을 마저 탐색하면되지만, for문을 돌면서 행이 넘어갈 경우에는 다시 시작 열부터 탐색해주어야한다. 탐색을 이어나가면서 만약 오른쪽에도 사다리가 없고 왼쪽에도 사다리가 없으면 사다리를 놓을 수 있는 것이므로, 사다리를 놓고나서 카운트수를 하나 증가시킨 채 DFS 재귀탐색을 진행한다. 백트래킹 조건에 걸리면 리턴되어 그 자리로 다시 돌아오므로 놓아버린 사다리를 제거해주는 작업을 꼭 해주어야한다. 

5) 구현코드   

#i번째줄이 i번째로 도착하는지 판단하는 함수 
def check(): 
    for start in range(N): #모든 시작점에 대해서 
        now = start 
        for j in range(H): 
            if board[j][now]: # 가로선이 오른쪽에 존재한다면
                now += 1 #오른쪽으로이동  
            elif now > 0 and board[j][now - 1]: # 가로선이 왼쪽에 존재한다면
                now -= 1 #왼쪽으로 이동 
        if now != start: #시작위치로 안돌아왔으면  
          return False  #불일치 
    return True


def dfs(cnt, x, y):
    global ans
    if check(): #조건만족하면 
        ans = min(ans, cnt) #최소값 업데이트 후 
        return #종료 
    elif cnt == 3 or ans <= cnt: #횟수가 3넘어가거나 최소값넘어가면
        return #종료 

    for i in range(x, H): #행
        if i == x: # 행이 변경되기 전에는
          now = y #지금 탐색중인 열부터 
        else: # 행이 변경될 경우
          now = 0  #가로선 처음부터 탐색

        for j in range(now, 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 


N, M, H = map(int, input().split()) #세로, 사다리, 가로 
board = [[False] * N for _ in range(H)] #사다리배열

for _ in range(M): 
  a, b = map(int, input().split())
  board[a - 1][b - 1] = True #사다리가 있는 곳 

ans = 4 #최대 정답값 
dfs(0, 0, 0) 
print(ans if ans < 4 else -1)

 

⭐️난이도:  골드 4⭐️

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

15684번: 사다리 조작