15684번 - 사다리 조작

문제

 

15684번: 사다리 조작 (acmicpc.net)

15684번: 사다리 조작

풀이 1

최대 3개 만큼 사다리를 놓아보며, 모든 i 번째 사다리의 도착지점이 i 인 경우 중 사다리를 가장 적게 놓는 경우를 찾아야 한다. 사다리를 타고 내려가는 상황을 이차원 리스트로 구현해야겠다는 판단을 떠올리는게 핵심이며, 이후엔 백트래킹으로 사다리를 놓아보면서 정해진 개수만큼 사다리를 다 놓으면 원하는 결과가 나오는지 확인하는 전형적인 부르트포스 혹은 탐색 문제가 된다. 이번 문제에선 다음과 같은 교훈을 얻었다.

1. 예시까지 꼼꼼히 확인해서 문제를 제대로 파악하는 습관을 가져야한다. 글자 그대로를 제대로 이해했다고 착각하여 많은 시간을 버리게 될 수 도 있다.
2. 구현 문제인 이상, 문제를 최대한 작은 단위로 분리해보며 내가 풀 수 있게 설계하자.

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


def check():
    for start in range(1, n+1):
        col = start
        for row in range(1, h+1):
            if ladders[row][col] == 1:
                col += 1
            elif ladders[row][col-1] == 1:
                col -= 1
        if start != col:
            return False
    return True


def put_ladders(cnt):
    global answer
    if cnt == limit or answer:
        answer |= check()
        return
    for row in range(1, h+1):
        for col in range(1, n):
            # 사다리를 놓을 수 있는 곳이고, 양 옆에 사다리가 존재하지 않을 때
            if ladders[row][col] == 0 and ladders[row][col-1] == 0 and ladders[row][col+1] == 0:
                ladders[row][col] = 1
                put_ladders(cnt+1)
                ladders[row][col] = 0


answer = False
for limit in range(4):
    put_ladders(0)
    if answer:
        print(limit)
        break
else:
    print(-1)

풀이 2

다시 풀어보며 많은 것을 배울 수 있었다.

먼저 이차원 리스트에서 좌표의 조합을 구할 때 중복되는 조합을 만드는것을 방지하는 방법인데, 다음 링크를 참고하자.

2차원 배열에서 조합 선택하기 :: Awesome (tistory.com)

2차원 배열에서 조합 선택하기

즉 일차원 리스트처럼 중복 방지를 위한 start를 계속해서 갱신해주되, 이차원 리스트에서는 시작 row가 같은 row일 때 일차원 리스트와 마찬가지로 이전 col 이후부터 탐색을 하고, 이후 row에서는 col = 0 부터 탐색하는 것이다. 매우 중요하니 잘 외워두자.

마찬가지로 중요한 것은 가지치기인데, 횟수가 최소가 되는 경우를 구해야하므로 cnt 가 answer 이상이 되는 경우들은 가지치기를 하는것이 좋다는 것이다.

또 이전에 풀었던것처럼 굳이 2배 스케일링을 하지 않고도 잘 풀 수 있으며, 메모리와 시간이 더 단축된다는 점도 알아두자.

N,M,H = map(int,input().split())
board = [[0]*2*(N+1) for _ in range(H+1)]
for _ in range(M):
    a,b = map(int,input().split())
    board[a][2*b+1] = 1


def check():
    global answer
    for col in range(2, 2 * N + 1, 2):
        ptr = col
        for row in range(1, H + 1):
            # 왼쪽
            if board[row][ptr - 1] == 1:
                ptr -= 2
            # 오른쪽
            elif board[row][ptr + 1] == 1:
                ptr += 2
        # i가 i로 가는지 확인
        if ptr != col:
            return False
    return True


def get_answer(cnt,sr,sc):
    global answer
    # 가지치기
    if cnt >= answer or cnt > 3:
        return
    if check():
        answer = min(answer, cnt)
        return
    # 사다리 놓아보기
    for row in range(sr,H+1):
        sc = sc if row == sr else 3
        for col in range(sc,2*N,2):
            if board[row][col] == 0 and board[row][col-2] == 0 and board[row][col+2] == 0:
                board[row][col] = 1
                get_answer(cnt+1,row,col+2)
                board[row][col] = 0


answer = int(1e9)
# 이차원 리스트에 대해 조합 구현
get_answer(0,1,3)
print(answer) if answer <= 3 else print(-1)