[15684] 사다리 조작

문제

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

풀이

먼저 가로선을 놓은 위치를 표시하기 위해 이차원 배열을 만들어주었습니다. 배열[i][j]는 j 번 세로선의 i 번 점선의 위치에 가로선의 유무를 의미합니다.

다음으로 가로선을 놓을 수 있는 모든 위치를 구해줍니다.

구한 위치들에서 조합을 구해 정답이 나올 때까지 구해주는 방식으로 진행했습니다. 조합은 combinations 함수를 사용하여 구해주었습니다.

import sys
from itertools import combinations

N, M, H = map(int, sys.stdin.readline().split())
lines = [[False] * (N + 1) for _ in range(H + 1)] # 가로선을 놓은 지점
remain = [] # 가로선을 놓을 수 있는 위치

for _ in range(M):
    a, b = map(int, sys.stdin.readline().split())
    lines[a][b] = True

# 가로선을 놓을 수 있는 위치 구하기
for r in range(1, H+1):
    for c in range(1, N): # 가장 오른쪽에 존재하는 세로선에는 가로선을 놓을 수 없기 때문에 N-1까지만
        if not lines[r][c]:
            remain.append((r, c))

result, count = sys.maxsize, 0

def move(start): # 시작 지점에서의 결과 반환
    current_r, current_c = 1, start
    while current_r <= H:
        if lines[current_r][current_c]: 
            current_c += 1
        elif lines[current_r][current_c-1]: 
            current_c -= 1
        current_r += 1
    return current_c

while count <= 3 and result == sys.maxsize:
    for positions in combinations(remain, count):
        for r, c in positions:
            lines[r][c] = True
        for i in range(1, N+1):
            if i != move(i):
                break
        else:
            result = count
            break
        for r, c in positions:
            lines[r][c] = False
    count += 1
print(result if result != sys.maxsize else -1)