백준 GOLD 3 [15684번] 사다리 조작 {언어 : Python}

문제 링크

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

내 코드

import sys
input = sys.stdin.readline
n, m, h = map(int, input().split())
board = [[0] * (n+1) for _ in range(h+1)]

for _ in range(m):
    row, column = map(int, input().split())
    board[row][column] = column + 1
    board[row][column+1] = column

def check(board, destination):
    c = destination
    for r in range(1, h+1):
        if board[r][c]:
            c = board[r][c]
    if c == destination:
        return True
    return False

def marking(board, destination):
    c = destination
    for r in range(1, h+1):
        if board[r][c]:
            c = board[r][c]
        else:
            board[r][c] = -1

def backtracking(board, column, cnt):
    global answer
    # 가지치기
    if answer <= cnt:
        return
    if column > n:
        answer = cnt
        return
    if check(board, column):
        marking(board, column)
        return backtracking(board, column+1, cnt)

    # 설치
    c = column
    for r in range(1, h+1):
        if board[r][c] > 0:
            c = board[r][c]
        else:
            right = c + 1
            left = c - 1
            # 왼쪽 설치
            # 왼쪽에 없어야 하고
            # 오른쪽이 n 이거나 오른쪽에서 현재 지점으로 선이 없어야 한다.
            if c > 1 and board[r][left] == 0 and ((right <= n and board[r][right] != c) or right > n):
                leftBoard = [line[:] for line in board]
                leftBoard[r][left] = c
                leftBoard[r][c] = left
                backtracking(leftBoard, column, cnt+1)
            if c < n and board[r][right] == 0 and ((left >= 1 and board[r][left] != c) or left < 1):
                rightBoard = [line[:] for line in board]
                rightBoard[r][right] = c
                rightBoard[r][c] = right
                backtracking(rightBoard, column, cnt+1)
answer = 4
backtracking(board, 1, 0)
print(answer if answer < 4 else -1)

효율적인 코드

from sys import stdin

def back_tracking(n: int, max_cnt: int):
    global ladder, answer, H, N

    if answer!=-1:
        return
    
    cur_cnt = check()
    if cur_cnt+(max_cnt-n)*2 < N:
        return
    
    if n==max_cnt:
        if cur_cnt==N:
            answer = max_cnt
        return
    
    for h in range(1, H+1):
        for i in range(1, N):
            if ladder[h][i]==0 and ladder[h][i+1]==0:
                ladder[h][i], ladder[h][i+1] = i+1, i
                back_tracking(n+1, max_cnt)
                ladder[h][i], ladder[h][i+1] = 0, 0

def check() -> int:
    global ladder, N, H
    matched = 0
    for i in range(1, N+1):
        cur_i = i
        for h in range(1, H+1):
            if ladder[h][cur_i]!=0:
                cur_i = ladder[h][cur_i]
        if cur_i==i:
            matched += 1
    return matched

N, M, H = map(int, stdin.readline().split())
ladder = [[0]*(N+1) for _ in range(H+1)]
for i in stdin:
    a, b = map(int, i.split())
    ladder[a][b] = b+1
    ladder[a][b+1] = b
answer = -1
for cnt in range(4):
    back_tracking(0, cnt)
    if answer != -1:
        break
print(answer)

풀이 방법

1. 사다리를 그린다.
   • 예를들어 3 2 라면
   • 3번 세로줄의 2번 행에서 우로 선이 이어진다.
   • board[3][2] = 2 + 1
     • 즉 오른쪽으로 이동할 수 있도록 방향을 적는다.
   • board[3][3] = 2
     • 오른쪽에서도 이동할 수 있도록 이쪽 지점을 적는다.
2. 세로 줄 하나가 출발점과 끝점이 같은지 확인하는 함수를 만든다.
3. 지나온 길을 마크할 수 있게 마킹 함수를 만든다.
   • 가로줄이 없는 세로 길에 이미 지나간 번호가 있다면 이 길을 건들면 안된다.
   • 가로선은 중복되서 지나갈 수 있지만 세로 선은 중복되지 않기 때문이다.
4. 백트래킹을 실시한다.
5. 실시후 answer의 값이 4이면 불가능하다는 말로 -1 아닌 경우는 answer값을 출력하면 끝!

느낀점

• 백트래킹을 할 때 깊은 복사를 자주 사용하는 것 같다.
• 이로인해 오히려 시간복잡도가 오르고 코드가 더 복잡해질 수 있다고 생각한다.
• 일단 풀었으면 된다라는 마인드가 아닌 왜 이렇게 풀었고 더 효율적인 방법은 없을지 찾는 과정이 필요하다.