[백준 15684] 사다리 조작

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

15684번: 사다리 조작

---

접근

먼저 사다리를 어떻게 모델링할 것인지 정했다. 사다리를 2차원 리스트로 표현하였다. 사다리를 타고 내려오다가 1을 만났을 때 오른쪽으로 이동하도록 하고, 왼쪽에 1이 존재하면 왼쪽으로 이동하도록 하였다. 따라서 2차원 리스트에서 1은 현재 위치와 오른쪽이 이어져있다는 의미이다.

이제 이를 활용하여 1번부터 N번까지 사다리를 타고 내려왔을 때 모든 열이 처음과 같은 위치를 가리키고 있을 때 사다리 조작에 성공했다고 정한다. 

 

구현

- 사다리를 2차원 리스트로 정의하고

- M개의 가로선의 위치를 입력받아 1로 표시한다.

N, M, H = map(int, input().split())
board = [[0 for _ in range(N + 1)] for _ in range(H + 1)]
for _ in range(M):
    a, b = map(int, input().split())
    board[a][b] = 1

- 열을 순서대로 탐색하면서 사다리를 타고 내려갔을 때 같은 위치를 가리키고 있는지 검사한다.

- 현재 위치가 1이라면 열을 오른쪽으로 이동하고 현재 위치의 왼쪽이 1이라면 왼쪽으로 이동시킨다.

- 만약 처음 출발한 열과 다르다면 False를 반환한다.

def isPossible(board):
    for x in range(1, N+1):
        nx = x
        for y in range(H+1):
            if board[y][nx]:
                nx += 1
            elif board[y][nx - 1]:
                nx -= 1
        if nx != x:
            return False
    return True

- 위의 함수를 활용하여 사다리에 가로선을 그리기 전에 검사하여 사다리 조작을 하지 않아도 되면 answer에 0을 대입한다.

- 아니라면 사다리에 선을 한 개부터 세 개까지 그어본다.

- 만약 answer가 그대로 4라면 3개로 충분하지 않거나 사다리 조작이 불가능하다는 것이기 때문에 -1을 대입한다.

answer = 4
if isPossible(board):
    answer = 0
else:
    for k in range(1, 4):
        solve(0, 1, 1, k)
        if answer != 4:
            break

if answer == 4:
    answer = -1
print(answer)

- 사다리를 탐색하여 가로선을 그을 수 있는 위치를 찾고 

- 해당 위치에 1로 표시 후에 재귀 호출을 진행한다.

def solve(picked, y, x, k):
    global answer
    if picked == k:
        if isPossible(board):
            answer = min(answer, picked)
        return

    for i in range(y, H + 1):
        for j in range(x, N):
            if board[i][j] == 0 and board[i][j-1] == 0 and board[i][j+1] == 0:
                board[i][j] = 1
                solve(picked+1, i, j, k)
                board[i][j] = 0
        x = 1

---

전체 코드

import sys
input = sys.stdin.readline

def isPossible(board):
    for x in range(1, N+1):
        nx = x
        for y in range(H+1):
            if board[y][nx]:
                nx += 1
            elif board[y][nx - 1]:
                nx -= 1
        if nx != x:
            return False
    return True

def solve(picked, y, x, k):
    global answer
    if picked == k:
        if isPossible(board):
            answer = min(answer, picked)
        return

    for i in range(y, H + 1):
        for j in range(x, N):
            if board[i][j] == 0 and board[i][j-1] == 0 and board[i][j+1] == 0:
                board[i][j] = 1
                solve(picked+1, i, j, k)
                board[i][j] = 0
        x = 1

N, M, H = map(int, input().split())
board = [[0 for _ in range(N + 1)] for _ in range(H + 1)]
for _ in range(M):
    a, b = map(int, input().split())
    board[a][b] = 1

answer = 4
if isPossible(board):
    answer = 0
else:
    for k in range(1, 4):
        solve(0, 1, 1, k)
        if answer != 4:
            break

if answer == 4:
    answer = -1
print(answer)