백준 15684번 사다리 조작 삼성 SW역량테스트 (Python)

백준 15684번 사다리 조작 문제 바로가기

문제 이해

처음 시작한 번호와 마지막 끝난 번호가 같도록 사다리를 조작해야한다.
우리는 이 조작을 위해서 가로선을 둘 수 있는데 가로선의 개수는 최대 3개까지 둘 수 있다.
만약 가로선이 3을 넘거나 조작을 통해 목표를 이룰 수 없다면 -1을 출력해야 하는 문제이다.

문제 접근

이 문제를 풀기 위해서 3가지 부분으로 나누었다.

• 사다리를 구현하기
• 1자로 내려오는지 확인하는 함수
• 가로선을 두면서 확인하는 DFS

문제 풀이

사다리를 구현하기

2차원 배열을 만들고 입력된 M개의 가로선을 각각 표시해주었다.

sadari = [[0] * N for _ in range(H)]
for i in range(M):
    a,b = map(int, sys.stdin.readline().split())
    sadari[a-1][b-1] = 1

1자로 내려오는지 확인하는 함수

이름은 빼빼로라 지었다! 1자로 내려와야되니까!
높이 H만큼 반복하는데 처음 시작점을 start_num이라 할 때 가로선에 따라서 start_num을 조작하고 최종적으로 끝까지 내려갔을 때 start_num과 i가 다르면 False를 리턴한다.

def bebero(): # 1자로 내려가는지 확인하는 함수 1자로 내려가면 True 아니면 False
    for i in range(N): # 처음 시작할 사다리 번호
        start_num = i   
        for j in range(H):
            if sadari[j][start_num]==1:
                start_num += 1
            elif start_num>0 and sadari[j][start_num-1] == 1:
                start_num -= 1    
        if i != start_num:
            return False
    return True

가로선을 두면서 확인하는 DFS

cnt는 추가한 가로선의 개수를 나타낸다.
따라서 cnt가 최소일 때를 저장한다.
만약 cnt가 고려하지 않아도 되는 값이라면 수행시간을 줄이기 위해서 함수를 종료한다. (return)
가로선을 생성하고 재귀함수를 통해 dfs를 구현한다.

def dfs(cnt, x, y):
    global answer
    if answer <= cnt:   
        return
    if bebero():      # i번 세로선의 결과가 i번이 나오는지 체크
        answer = min(answer, cnt)
        return
    if cnt > 3:
        return
    for i in range(x, H): 
        for j in range(k, N - 1):
            if sadari[i][j] == 0: # 가로선이 없다면 생성
                sadari[i][j] = 1
                dfs(cnt + 1, i, j + 2) # 바로 옆에 이어지지 않도록 j+2 
                sadari[i][j] = 0 원상복구

제출 코드

import sys
N,M,H = map(int, sys.stdin.readline().split())
sadari = [[0] * N for _ in range(H)]
for i in range(M):
    a,b = map(int, sys.stdin.readline().split())
    sadari[a-1][b-1] = 1


# 1자로 내려가는지 확인하는 함수 = bebero
# 가로선 개수 0개부터 3개까지 생성하고 bebero 함수 실행 완전탐색
def bebero(): # 1자로 내려가는지 확인하는 함수 1자로 내려가면 True 아니면 False
    for i in range(N): # 처음 시작할 사다리 번호
        start_num = i   
        for j in range(H):
            if sadari[j][start_num]==1:
                start_num += 1
            elif start_num>0 and sadari[j][start_num-1] == 1:
                start_num -= 1    
        if i != start_num:
            return False
    return True
def dfs(cnt, x, y):
    global answer
    if answer <= cnt:   # 가로선을 정답보다 많이 만든 경우 확인 필요 x
        return
    if bebero():      # i번 세로선의 결과가 i번이 나오는지 체크
        answer = min(answer, cnt)
        return
    if cnt == 3:
        return
    for i in range(x, H): 
        for j in range(0, N - 1):
            if sadari[i][j] == 0: # 0인 경우 가로줄 만들고, 연속된 가로선을 만들지 않기 위해 j + 2호출
                sadari[i][j] = 1
                dfs(cnt + 1, i, j + 2)
                sadari[i][j] = 0
answer = 4
dfs(0,0,0)
if answer>3:
    answer = -1
print(answer)