[백준/python] 15684번: 사다리 조작

문제

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

15684번: 사다리 조작

---

문제 요약

N개의 세로선과 M개의 가로선으로 이루어져 있는 사다리 게임이 있다.

 

가로선을 놓을 수 있는 점선의 개수는 H이다.

 

가로선을 추가해서 i번 세로선의 결과가 i번이 나오도록 하기 위해 필요한 가로선 개수의 최소값을 출력한다.

 

가장 위에 있는 점선의 번호와 가장 왼쪽에 있는 세로선의 번호는 1번이다.

 

+ 가로선은 두 개이상 연속할 수 없다.

---

코드

import sys
input = __import__('sys').stdin.readline

def check():
# i번 세로선이 i번으로 도착하는지 확인
    for start in range(N):
    # 1번 부터 N번 세로선까지 검사
    # start는 출발 좌표이자 도착해야하는 좌표
        j = start
        # j는 현재 몇번째 열(세로선)에 있는지 표시하는 좌표

        for i in range(H):
        # 가로선(행) 이동
            if board[i][j]:
            # 현재 열에 가로선의 좌표가 표시되어 있다면,
               j += 1
               # 오른쪽 열로 이동
            elif j > 0 and board[i][j - 1]:
            # 현재 열 바로 왼쪽 열에 가로선 좌표가 표시되어 있다면,
                j -= 1
                # 왼쪽 열로 이동

        if j != start:
        # 가장 하단 까지 왔는데 시작했던 열 좌표가 아니라면,
            return False
            # 원하는 결과가 아니므로 False 반환
    return True

def dfs(cnt, x, y):
    # cnt는 추가한 가로선의 개수, x와 y는 현재 검사하는 좌표
    global ans
    if check():
    # 현재 상태에서 각 출발점의 열 좌표와 도착점의 열 좌표가 같다면
        ans = min(ans, cnt)
        # 저장되어 있던 ans값과 비교하여 재설정
        return
    elif cnt == 3 or ans <= cnt:
    # 추가한 가로선의 개수가 3개인데 위 조건문에서 조건에 부합하지 않았을 경우 그다음 호출에서 4개가 됨으로 조건 위반
    # 추가한 가로선의 개수가 이전에 저장했던 ans값보다 클 경우 더이상 볼 필요 X
        return
    for i in range(x, H):
    # i는 현재 가로선을 추가할 행, x는 현재 검사하는 행
        if i == x: 
        # 같은 행에서 계속해서 가로선을 추가하려는 상황
            k = y
            # y열부터 계속해서 검사
        else:
        # 새로운 행에서 계속해서 가로선을 추가하려는 상황
            k = 0 
            # 0열부터 다시 검사
        for j in range(k, N - 1):
            if not board[i][j - 1] and not board[i][j] and not board[i][j + 1]:
            # 가로선을 추가하려는 인덱스와 그 왼쪽, 오른쪽 인덱스에 아직 가로선이 없다면
                board[i][j] = 1 # 가로선 놓기
                dfs(cnt + 1, i, j + 2)
                # 가로선을 연속으로 놓을 수 없으므로 j + 2부터 검사
                board[i][j] = 0 # 가로선 없애기

N, M, H = map(int, input().rstrip().split())
# N은 세로선의 개수, M은 가로선의 개수, H는 가로선을 놓을 수 있는 위치의 개수
# 세로선과 가로선의 인덱스는 1부터 시작

if M == 0:
    print(0)
    exit()
# M이 0일 경우 출발점에서 도착점으로 바로 내려오므로 0 출력 후 종료

# 현재 사다리 구현
board = [[0] * N for _ in range(H)]
for _ in range(M):
# 가로선 정보 입력 받기
    a, b = map(int, input().rstrip().split()) 
    board[a - 1][b - 1] = 1
    # 사다리에 가로선(왼쪽 끝자락)이 있으면 1, 없으면 0
    # 가로선은 왼쪽 끝자락만 표시한다.

ans = 4
# 최소 추가선 개수

dfs(0, 0, 0)

if ans > 3:
    ans = -1

print(ans)

---

코드 설명

1. 사다리 게임의 판을 구현한 2차원 배열 board를 생성한다.

+ board[i][j]가 1이면 i번째 점선과 j번째 세로선의 교점과 i번째 점선과 j+1번째 세로선의 교점을 각각 가로선의 왼쪽 끝, 오른쪽 끝으로 하는 가로선이 존재한다.

+ 우리가 사용하는 board의 점선과 세로선은 0번부터 시작한다.

 

2. ans는 문제 조건을 만족하기 위해 필요한 가로선의 개수이다.

+ 초기 값을 4로 설정한다. (ans보다 작은 개수로 업데이트 해야 하므로)

+ 모든 경우의 수를 검사해도 조건을 만족하는 경우가 없다면 -1로 변경하여 출력한다.

 

3. check 함수는 board의 세로선들을 하나씩 검사하여 i번 세로선 상단에서 출발하여 하단까지 왔을 때 i번 세로선 위에 있는지를 검사한다.

 

4. dfs 함수는 (0, 0)부터 가로선을 추가할 수 있는 모든 인덱스를 검사하여 추가하고, 다음으로 추가할 수 있는 인덱스를 dfs 인자에 넣고 자신을 다시 호출한다. (재귀)

 

4-1. check 함수를 호출하여 현재 상태가 문제 조건에 맞는 상태라면 현재까지 추가한 가로선 수와 ans값을 비교하여 업데이트하고 함수를 종료한다.

 

4-2. 추가한 가로선의 개수가 3개이거나 이전 ans값보다 크다면 더이상 볼 필요가 없으므로 함수를 종료한다.