[BOJ] Q15684 사다리 조작

[BOJ] Q15684 사다리 조작

Question

Language: Python

Difficulty: Gold 3

가능한 경우의 수를 모두 점검하는 bruteforce 유형의 문제이다.

가로선은 항상 왼쪽에서 오른쪽으로 긋는다고 생각하고, 출발점에 대해서만 마킹한 graph를 저장한다.

그렇게 되면, 자기 기준으로 왼쪽, 오른쪽에 마킹이 되어 있는 경우 해당 자리에는 가로선을 추가할 수 없다 (연속된 가로선은 존재할 수 없는 것이 문제의 조건이다) 그렇게 가로선을 추가해가면서 사다리타기를 진행했을 때 i 번째 세로줄에서 시작한 경우 i 번째 세로줄에서 끝나는지 점검한다.

사다리 타기 게임의 경우, 오른쪽으로 가로선이 있는 경우 오른쪽으로 이동 후 아래로 이동하고, 왼쪽으로 가로선이 있는 경우 왼쪽으로 이동한 후 아래로 이동한다.

def propose_ladder_game():
    for i in range(1,N+1):
        row,col=1,i

        while row <= H:
            #왼쪽으로 가로선이 있는 경우
            if graph[row][col-1]==True:
                col=col-1
            #오른쪽으로 가로선이 있는 경우
            elif graph[row][col]==True:
                col=col+1

            row=row+1
        if col !=i:
            return False

    return True

그리고, 최대 가로선의 개수는 3개이므로, 3개를 넘어서는 경우 추가적인 탐색을 멈춘다.

Solution

from math import inf

min_result=inf

def propose_ladder_game():
    for i in range(1,N+1):
        row,col=1,i

        while row <= H:
            #왼쪽으로 가로선이 있는 경우
            if graph[row][col-1]==True:
                col=col-1
            #오른쪽으로 가로선이 있는 경우
            elif graph[row][col]==True:
                col=col+1

            row=row+1
        if col !=i:
            return False

    return True

def print_graph():
    for i in range(1,H+1):
        print(graph[i])

def dfs(count):
    global min_result

    if count >3:
        return

    if propose_ladder_game():
        min_result=min(min_result,count)
        return
    
    for row in range(1,H+1):
        for col in range(1,N):
            if graph[row][col-1] == False and graph[row][col] == False and graph[row][col+1] == False:
                graph[row][col] = True
                dfs(count+1)
                graph[row][col] = False


하지만, 위와 같이 풀이를 진행하게 되면, 시간초과가 발생한다.

매 호출마다 이중 for문을 통해 모든 좌표를 비교하게 되면서 반복횟수가 너무 많아진다.

따라서, 이전까지 조사한 마지막 행의 값을 추가 인자로 전달한다. 이렇게 하면 이전 행에서부터 반복을 진행하면 되므로 반복 횟수를 줄일 수 있다. 단, 열도 전달하게 되면 안된다. 다음 행 부터는 다시 첫 열을 조사해야한다.

```python
for row in range(idx,H+1):
    for col in range(1,N):
        if graph[row][col-1] == False and graph[row][col] == False and graph[row][col+1] == False:
            graph[row][col] = True
            dfs(count+1,row)
            graph[row][col] = False

이렇게 까지하면 시간 내에 풀이를 할 수 있다. 여기에 추가적으로 추가되는 가로에 대해서 가로선이 0개 추가되는 경우 가로선이 1개 추가되는 경우 가로선이 2개 추가되는 경우 가로선이 3개 추가되는 경우 위의 4가지 경우를 순서대로 진행하게 되면, dfs 호출 횟수를 줄일 수 있게된다. 가로선이 적은 경우에서 이미 문제 조건에 부합하는 경우가 존재하면, 더 이상 가로선을 늘릴 필요가 없게 된다.

Perfect Solution

from math import inf
min_result=inf

def propose_ladder_game():
    for i in range(1,N+1):
        row,col=1,i

        while row <= H:
            #왼쪽으로 가로선이 있는 경우
            if graph[row][col-1]==True:
                col=col-1
            #오른쪽으로 가로선이 있는 경우
            elif graph[row][col]==True:
                col=col+1

            row=row+1
        if col !=i:
            return False

    return True

def print_graph():
    for i in range(1,H+1):
        print(graph[i])

def dfs(count,last_row,added_lines):
    global min_result

    if count == added_lines:
        if propose_ladder_game():
            min_result=count
        return
    
    for row in range(last_row,H+1):
        for col in range(1,N):
            if graph[row][col-1] == False and graph[row][col] == False and graph[row][col+1] == False:
                graph[row][col] = True
                dfs(count+1,row,added_lines)
                graph[row][col] = False


def solution():

    for i in range(4):
        dfs(0,1,i)
        if min_result != inf:
            break

    if min_result == inf:
        return -1
    
    return min_result

if __name__ == "__main__":
    N,M,H=map(int,input().split())
    graph=[[False] *(N+1) for _ in range(H+1)]
    for _ in range(M):
        a,b=map(int,input().split())
        graph[a][b]=True
    
    print(solution())