[BOJ]15684 사다리 조작

[문제 링크]

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

[풀이]

답을 찾는 방법 자체는 m과 h가 그다지 크지 않기 때문에 브루트 포스로 가로선을 놓아 풀면 되는 문제로 보였다.

다만 사다리와 가로선 설치, 사다리를 타고 내려가는 법칙(?)을 어떻게 쉽게 구현해내느냐가 문제의 열쇠인 것 같다.

필자는 세로선을 1로 표현하고 세로선 사이사이 0 으로 간격을 만들고 가로선이 존재한다면 간격에 1을 쓰는 방향으로 구현했다.

또한 구현의 편의를 위해 마지막에 행 하나를 추가했다.(이유는 뒤에 나옵니다)

만약 사다리가 이런 모양이라면 아래와 같은 배열로...

[
  [1, 1, 1, 0, 1, 0, 1, 0, 1],
  [1, 0, 1, 0, 1, 1, 1, 0, 1],
  [1, 0, 1, 1, 1, 0, 1, 0, 1],
  [1, 0, 1, 0, 1, 0, 1, 0, 1],
  [1, 1, 1, 0, 1, 0, 1, 1, 1],
  [1, 0, 1, 0, 1, 0, 1, 0, 1],
  [1, 0, 1, 0, 1, 0, 1, 0, 1],
]

가로선은 combinations 모듈을 이용하여 골랐다.(이 과정에서 가로선이 동시에 두 개 놓이는 경우를 배제하여야 함)

가로선을 놓은 후 원하는 사다리 결과가 나오는지 확인하는 함수는 BFS를 이용하여 가로선이 존재한다면 현재 좌표에서 x축 옆으로 두칸, y축 앞으로 한 칸으로 이동하는 규칙에 따라 짜주었다.

여기서 마지막 행에서 가로선을 만나면 y축 방향으로 인덱스 에러가 날 수 있어서 배열을 만들 때에 행을 하나 추가해준 것입니다.

[정답 코드]

from itertools import combinations

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

vertical = [list(map(int, input().split())) for _ in range(m)]

convert_v = list(map(lambda x: [x[0] - 1, (x[1] * 2) - 1], vertical))

board = [[0] * (n * 2 - 1) for _ in range(h + 1)]
width = (n * 2) - 1

for i in range(h + 1):
    for j in range(len(board[0])):
        if j % 2 == 0:
            board[i][j] = 1

for r, c in convert_v:
    board[r][c] = 1


def is_equal(i):
    cr, cc = 0, i * 1
    while cr < h + 1:
        if cc < width - 1:
            if board[cr][cc + 1] == 1:  # 오른쪽 가로선
                cc += 2
                cr += 1
                continue
        if cc > 1:
            if board[cr][cc - 1] == 1:  # 왼쪽 가로선
                cc -= 2
                cr += 1
                continue
            # 가로선이 없음
        cr += 1
    if cc == i:
        return True
    else:
        return False


mylist = []  # 가로선을 놓을 수 있는 칸(좌표)

for r in range(h):
    for c in range(1, width, 2):
        if n == 2:
            if board[r][c] == 0:
                mylist.append([r, c])
        elif c == 1:
            if board[r][c] == 0 and board[r][c + 2] == 0:
                mylist.append([r, c])
        elif c == width - 2:
            if board[r][c] == 0 and board[r][c - 2] == 0:
                mylist.append([r, c])
        else:
            if board[r][c] == 0 and board[r][c - 2] == 0 and board[r][c + 2] == 0:
                mylist.append([r, c])


def solve():

    if m == 0:
        return 0
    equal = True

    for i in range(0, width, 2):
        if not is_equal(i):
            equal = False
            break
    if equal == True:
        return 0

    for num in range(1, 4):  # 놓을 사다리 수

        for comb in combinations(mylist, num):
            equal = True
            for r, c in comb:  # 가로선 설치
                board[r][c] = 1

            for i in range(0, width, 2):
                if not is_equal(i):
                    equal = False
                    break
            if equal == True:
                return num

            for r, c in comb:  # 가로선 철거
                board[r][c] = 0
    return -1


print(solve())