사다리 조작

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

15684번: 사다리 조작

문제요약:

우리가 익히 알고있는 사다리 타기이다. 이때 사다리의 관한 정보는 미리 주어지고 최대 3개의 추가적인 사다리를 설치할 수 있는데, 이때 한사다리의 양옆에는 사다리가 존재할 수 없을때, 모든 시작지점들이 각각의 같은 순서의 도착지점으로 도착하기까지 필요한 추가 사다리의 최소개수를 구하시오.

 

소요시간:

@ + 30분

골드3

 

코딩:

import sys
input= sys.stdin.readline

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

arr = [[0]*(n-1) for _ in range(h)]

for _ in range(m):
    a,b = map(int,input().split())
    arr[a-1][b-1] = 1
    
#각 순서가 출발하여 도착지점과 출발지점이 모두 같을때 True아니라면 False
def go():
    for j in range(n):
        ori = j
        for i in range(h):
            if (j!=0 and arr[i][j-1]):
                j-=1
            elif (j!=n-1 and arr[i][j]):
                j+=1      
        if j != ori:
            return False
    else:
        return True
piv = 0       

# 추가적으로 사다리 설치하기
def make_stride(key,num,cnt):
    global piv
    
    if piv:
        return
        
    #원하는 개수만큼 설치했을때 원하는대로라면 리턴    
    if num == key:
        if go():
            piv = key 
        return
    #아직 다 설치하지 못했다면 직전에 설치한 지점 다음부터 설치
    for i in range(cnt,(n-1)*h):
        y = i//(n-1)
        x = i%(n-1)
        #양옆에 사다리가 있거나 이미 사다리가 있다면 패스
        if (x!=0 and arr[y][x-1]) or (x!=n-2 and arr[y][x+1]) or arr[y][x] :
            continue
        else:
            #사다리설치
            arr[y][x] = 2
            make_stride(key,num+1,i)
            arr[y][x] = 0

if go():
    print(0)
else:
    for i in range(1,4):
        make_stride(i,0,0)
        if piv:
            print(piv)
            break
    else:
        print(-1)

 

저번 연구소 문제에서 순서대로 n개의 벽을 효율적으로 설치 했을 때와 같은 dfs문제입니다. 사다리의 조건(양옆에 있을수 없음)에 따라 조건을 설정하고 나머진 똑같이 사다리를 설치해 주었습니다. 물론 위의 코드처럼 한개를 전부 설치하고, 없다면 2,3개 이런식으로 할수도 있지만, 3개를 설치할 때 사실 1,2개 설치가 포함됨으로, 처음부터 3개를 설치하고 확인을 3개 이하일 때 해주어도 무방합니다.