[백준] 사다리 조작

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

15684번: 사다리 조작

 

1. 문제 이해

가로선과 세로선이 주어지고 사다리 타기를 하는 문제. 주어진 가로선과 최대 3개의 가로선을 추가했을 때 i번째 열에서 시작했을 때 i번째 열로 끝나도록 해야합니다.

2. 문제 접근

조합을 이용하여 풀이했습니다. 조합으로 가로선이 놓을 수 있는 위치를 골라서 놓아보고 시뮬레이션으로 원하는 조건에 맞도록 결과가 나오는지 체크하였습니다. 주의해야할 점은 조합을 구할 때에 연속으로 가로선이 놓이면 안된다는 점 그리고 이미 가로선이 놓여져있는 위치는 빼고 조합을 구해야한다는 점입니다.

3. 풀이

import sys
from itertools import combinations
#sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

n, m, h = tuple(map(int, input().split()))

# ladder[i][j]: j열의 i번째에 가로선이 있는지
ladder = [
    [False] * n
    for _ in range(h)
]

row = set()
for i in range(m):
    y, x = tuple(map(int, input().split()))
    ladder[y - 1][x - 1] = True
    row.add((y - 1, x - 1))

pos = [
    (y, x) for y in range(h) for x in range(n - 1) if (y, x) not in row
]

def isPossible():
    for j in range(n):
        start = j
        col = j
        row = 0

        while row < h:
            # 오른쪽 가로선 체크
            if ladder[row][col]:
                col += 1
                row += 1
            # 왼쪽 가로선 체크
            elif col > 0 and ladder[row][col - 1]:
                col -= 1
                row += 1
            # 가로선이 없는 경우
            else:
                row += 1
        # 시작과 열이 달라지면 실패
        if start != col:
            return False

    return True

# 사다리를 놓지 않고도 가능한지 체크
if isPossible():
    print(0)
    sys.exit(0)

# 인접한 가로선이 있는지 체크
def hasSameHeight(comb):
    for i in range(len(comb)):
        cur = comb[i]
        nxt = comb[(i + 1) % len(comb)]

        if cur[0] == nxt[0] and abs(cur[1] - nxt[1]) == 1:
            return True

    return False

for c in range(1, 4):
    combs = list(combinations(pos, c))
    for comb in combs:
        if c > 2 and hasSameHeight(comb):
            continue

        for y, x in comb:
            ladder[y][x] = True

        # 사다리 체크
        if isPossible():
            print(c)
            sys.exit(0)


        for y, x in comb:
            ladder[y][x] = False

print(-1)