[ 백준 15684 ] 사다리 조작 - Python

문제 보기

이 문제는 시뮬레이션 문제이다.

 

문제를 읽고 어떤 알고리즘을 사용해야 할지 바로 떠오르지 않았다. 10분 넘게 고민하여도 도저히 생각이 안 났다. 완전 탐색을 하면 경우의 수가 너무 많아서 시간 초과가 날 것 같았지만 다른 방법이 떠오르지 않았다. 운이 좋은건지는 모르겠지만 정답은 완전 탐색이었다.

 

[ 케이스 분류]

문제에서 요구하는 정답이 1, 2, 3 혹은 -1(추가 x, 추가 4개 이상)이기 때문에 5가지로 분류하였다.

1. 가로선 추가 x

2. 가로선 1개 추가

3. 가로선 2개 추가

4. 가로선 3개 추가

5. 그 외

 

[ 가로선 추가 관리 ]

가로선을 추가하기 위해서 가로선을 추가할 수 있는 구간을 따로 저장하였다. 저장한 구간에서 파이썬 내장 함수 combination을 사용하여 1, 2, 3개를 고르는 모든 경우의 수를 구하였고 인접한 지역에 가로선이 있는지 확인한 후 조건을 만족한다면 가로선을 추가하였다.

 

[ 사다리 이동 ]

사다리는 2차원 배열을 활용하였으며 0과 1의 값을 가지고 있다. 1의 값을 가지는 경우는 오른쪽과 연결되어 있다고 생각하면 된다. 예를 들어서 현재 위치가 i, j일 때는 arr [i + 1][j]와 arr [i +1][j - 1]을 확인하면 된다. arr [i + 1][j] 값이 1이면 오른쪽으로 이동, arr [i + 1][j - 1]이 1이면 왼쪽으로 이동한다.

 

코드

import sys
from itertools import combinations


# 각 열을 움직였을때 결과 확인
def move():
    for i in range(1, N + 1):
        index = [0, i]  # 출발시 가로, 세로

        while index[0] < H:
            if connect[index[0] + 1][index[1]] == 1:  # 오른쪽 이동
                index[1] += 1
            elif index[1] - 1 >= 0 and connect[index[0] + 1][index[1] - 1] == 1:  # 왼쪽으로 이동
                index[1] -= 1
            index[0] += 1
        if index[1] != i:
            return 0
    return 1


# 인접 체크
def check(arr1, arr2):
    if arr1[0] == arr2[0]:
        if abs(arr1[1] - arr2[1]) == 1:
            return True
    return False


# 가로선 추가 상황 구현
def find():
    if M == 0 or move():   # 이미 구현된 상황
        return 0
    else:
        # 1개 추가로 가능한 상황
        for i in range(len(add)):
            row, col = add[i]
            connect[row][col] = 1
            if move():
                return 1
            else:
                connect[row][col] = 0

        # 2개 추가로 가능한 상황
        order = list(combinations(add, 2))
        for i in range(len(order)):
            if check(order[i][0], order[i][1]):  # 인접 확인
                continue
            connect[order[i][0][0]][order[i][0][1]] = 1
            connect[order[i][1][0]][order[i][1][1]] = 1
            if move():
                return 2
            else:
                connect[order[i][0][0]][order[i][0][1]] = 0
                connect[order[i][1][0]][order[i][1][1]] = 0

        # 3개 추가로 가능한 상황
        order = list(combinations(add, 3))
        for i in range(len(order)):
            if check(order[i][0], order[i][1]) or check(order[i][0], order[i][2]) or check(order[i][1], order[i][2]):
                continue
            connect[order[i][0][0]][order[i][0][1]] = 1
            connect[order[i][1][0]][order[i][1][1]] = 1
            connect[order[i][2][0]][order[i][2][1]] = 1
            if move():
                return 3
            else:
                connect[order[i][0][0]][order[i][0][1]] = 0
                connect[order[i][1][0]][order[i][1][1]] = 0
                connect[order[i][2][0]][order[i][2][1]] = 0

        # 나머지 상황
        return -1


if __name__ == "__main__":

    # input
    N, M, H = map(int, sys.stdin.readline().split())
    line = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]  # 가로선의 정보
    connect = [[0] * (N + 1) for _ in range(H + 1)]  # 전체 연결 정보

    # line 정보 -> connect 반영
    for i in range(len(line)):
        connect[line[i][0]][line[i][1]] = 1

    # 가로선 추가 가능한 영역 찾기
    add = []
    for i in range(1, H + 1):
        for j in range(1, N):
            if not (connect[i][j - 1] or connect[i][j] or connect[i][j + 1]):
                add.append([i, j])

    print(find())