백준 사다리 조작 [15684] 파이썬(Python) 코드 + 해설

백준 15684 사다리 조작 문제

이 문제는 메모리 초과와 시간 초과가 굉장히 많이 나는 문제입니다.

 

문제 소개

사다리 조작은 세로선과 가로선으로 이루어진 사다리 게임을 조작하여, 각 세로선의 결과가 자기 자신이 되도록 만드는 문제입니다. 세로선의 개수 N, 가로선을 놓을 수 있는 위치의 개수 H, 이미 놓인 가로선의 개수 M이 주어집니다. 최대 3개의 가로선을 추가하여 원하는 결과를 얻을 수 있는 최소의 가로선 개수를 구하는 것이 목표입니다.

• 입력 조건:
  • 세로선의 개수 N: 2≤N≤102 
  • 가로선을 놓을 수 있는 위치의 개수 H: 1≤H≤30
  • 이미 놓인 가로선의 정보 M개
• 출력 조건:
  • 추가해야 하는 가로선의 최소 개수 (단, 3개를 초과하면 -1을 출력)

 

문제 분석

이 문제는 가능한 모든 가로선의 조합을 탐색하여 원하는 결과를 찾는 완전 탐색(Brute Force) 문제입니다. 하지만 가능한 모든 조합을 시도하면 시간 초과가 발생할 수 있으므로, 효율적인 탐색 방법이 필요합니다.

• 가로선을 추가할 수 있는 최대 위치의 수:
  • 최대 (N−1)×H개의 위치에 가로선을 추가할 수 있습니다.
  • 하지만 N과 H의 최대값이 작기 때문에 모든 경우를 탐색할 수 있습니다.

해결 방법

1. 백트래킹(Backtracking)과 DFS를 이용한 탐색

• 재귀 함수를 사용하여 가로선을 추가하는 모든 경우를 탐색합니다.
• 현재까지 추가한 가로선의 개수가 3개를 넘지 않도록 제한합니다.
• 각 단계에서 사다리 게임의 결과를 확인하여 조기 종료합니다.

2. 가지치기(Pruning)를 통한 탐색 효율화

• 이미 현재 단계에서 답을 찾을 수 없으면 더 이상 탐색하지 않습니다.
• 현재까지 추가한 가로선의 개수가 최소값 이상이면 더 이상 탐색하지 않습니다.
• 인접한 위치에 가로선을 놓을 수 없도록 조건을 확인하여 불필요한 탐색을 줄입니다.

3. PyPy3를 이용한 시간 초과 해결

• Python은 인터프리터 언어로 실행 속도가 느릴 수 있습니다.
• PyPy3는 Just-In-Time 컴파일을 통해 Python 코드를 빠르게 실행할 수 있습니다.
• 따라서 동일한 코드라도 PyPy3로 제출하면 시간 초과를 피할 수 있습니다.

최종 파이썬 코드

import sys
input = sys.stdin.readline

# 입력 받기
N, M, H = map(int, input().split())
ladder = [[-1] * N for _ in range(H)]  # 각 위치의 연결 정보를 저장 (-1은 연결 없음)

# 기존 가로선 정보 추가
for _ in range(M):
    a, b = map(lambda x: int(x) - 1, input().split())
    ladder[a][b] = b + 1
    ladder[a][b + 1] = b

# 사다리 게임 결과 확인 함수
def check():
    for start in range(N):
        k = start  # 현재 위치
        for i in range(H):
            if ladder[i][k] != -1:
                k = ladder[i][k]  # 연결된 세로선으로 이동
        if k != start:
            return False
    return True

# 백트래킹을 이용한 가로선 추가 함수
def dfs(count, x, y):
    global min_count
    if count >= min_count:  # 가지치기: 현재까지의 가로선 수가 최소값 이상이면 종료
        return
    if check():
        min_count = count
        return
    if count == 3:  # 가로선을 3개까지 추가 가능
        return
    for i in range(x, H):
        k = y if i == x else 0
        for j in range(k, N - 1):
            if ladder[i][j] == -1 and ladder[i][j + 1] == -1:
                # 가로선 추가
                ladder[i][j] = j + 1
                ladder[i][j + 1] = j
                dfs(count + 1, i, j)
                # 가로선 제거 (백트래킹)
                ladder[i][j] = -1
                ladder[i][j + 1] = -1
        y = 0  # 다음 행부터는 y를 0으로 초기화

# 결과 출력
min_count = 4  # 가능한 최대 가로선 수 + 1로 초기화
dfs(0, 0, 0)
print(min_count if min_count <= 3 else -1)

코드 설명

입력 처리 및 초기화

• 사다리 상태 배열 초기화:
  • ladder[i][j]는 i번째 가로선 위치에서 j번 세로선과 연결된 세로선을 나타냅니다.
  • 연결이 없으면 -1, 연결이 있으면 연결된 세로선 번호를 저장합니다.
• 기존 가로선 정보 입력:
  • 이미 놓여 있는 가로선 정보를 ladder 배열에 반영합니다.
  • 양쪽 세로선의 연결 정보를 모두 저장합니다.

사다리 게임 결과 확인 함수 check()

• 각 세로선에 대해 사다리 게임을 진행하여 시작 세로선과 도착 세로선이 같은지 확인합니다.
• 모든 세로선이 자기 자신으로 돌아오면 True를 반환하고, 그렇지 않으면 False를 반환합니다.

백트래킹 함수 dfs(count, x, y)

• count: 현재까지 추가한 가로선의 개수
• (x, y): 가로선을 추가할 수 있는 위치를 탐색하기 위한 시작점
• 가지치기:
  • 현재 count가 최소 가로선 개수 이상이면 더 이상 탐색하지 않습니다.
  • 가로선을 3개까지 추가할 수 있으므로 count가 3이면 종료합니다.
• 가로선 추가 및 백트래킹:
  • 가로선을 추가할 수 있는 위치를 탐색하여 가로선을 추가합니다.
  • 가로선을 추가할 때, 인접한 위치에 가로선이 없는지 확인합니다.
  • 추가 후 재귀적으로 다음 가로선을 추가합니다.
  • 재귀 호출이 종료되면 가로선을 원래 상태로 복구합니다.

결과 출력

• 최소 가로선 개수가 3 이하이면 그 값을 출력합니다.
• 그렇지 않으면 -1을 출력합니다.

 

추가적으로 Python과 PyPy의 차이점에 대해 소개해드리겠습니다.

Python과 PyPy의 차이점

• Python은 인터프리터 언어로, 실행 속도가 상대적으로 느립니다.
• PyPy는 Python 코드를 Just-In-Time 컴파일하여 빠르게 실행할 수 있는 대안적인 구현체입니다.
• 특히 반복문과 재귀 호출이 많은 코드에서 PyPy의 성능이 더욱 돋보입니다.

 

15684 사다리 조작 시간초과와 런타임 에러

 

도움이 되셨다면 공감과 댓글 부탁드립니다.