[Python] 백준_사다리조작(15684)

문제

 

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

15684번: 사다리 조작

 

 

풀이

 

못풀겠어서 다른 분들의 풀이를 참고하였음.

처음에는 규칙을 찾으려고 했었지만, 각 열 별로 짝수의 라인이 있고 그 안에도 짝수 개의 라인이 있다면 가능하지않을까싶었는데 힘들었음.

 

그래서 다른 분들의 풀이와 동일하게 모든 경우를 다 따져보기로했음.                               

 

우선, solution함수 안에서 가장 처음에 check라는 함수를 실행해서 사다리를 전부 돌렸을 때 자신의 위치로 오는지 확인함.

세로 줄을 기준으로 확인하는데, i를 start라는 값에 할당함.

 

반복문을 돌면서 줄이 있으면 오른쪽 줄로, 줄이 없으면 왼쪽에 줄이 있는지 확인해줌. 사다리의 특성 상 두 개의 줄이 같은 줄에서 연속될 수 없기 때문에 가능함. -- 모양

 

이 check함수의 반환값이 True라면 문제의 조건을 만족한 것이므로 result의 값을 수정함.

 

 

 

다음은 solution함수임. 우선 파라미터로 count, nh,nn을 받았음. count는 추가한 사다리의 수, nh와 nn은 재귀를 사용할때 이어서 진행하므로 좌표값을 나타냄.

 

이번엔 check때와 달리 가로 줄 하나를 먼저 탐색함. 재귀이기때문에 가장 먼저 종료 조건을 설정해야함. check도 설정해줬지만, count가 3이라거나 result가 count보다 작은 경우엔 더 이상 진행할 필요가 없으므로 return

 

이제 본격적으로 줄을 탐색하는데 i는 가로줄이고, j는 세로줄이라고 생각하면됨.

사다리를 추가하다가 다음 가로줄로 넘어가면 다시 세로줄을 0부터 확인해야함. 그래서 i가 nh(이전에 진행하던 줄)이랑 같으면 그냥 이어서 nn으로 진행하면되고, 아닌경우엔 0부터 다시 확인하면됨.

 

사다리를 추가할 땐, 왼쪽과 오른쪽에 사다리가 없는지 확인 후에 추가하고, 사다리를 추가하게되면 다음 세로줄에는 추가할 수 없으므로 j에는 2를 더해줘서 다시 solution을 호출함.

 

import sys
input = sys.stdin.readline

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

ladder = [[False for _ in range(n)] for _ in range(h)]
result = 4
for _ in range(m):
    a, b = map(int,input().split())
    ladder[a - 1][b - 1] = True
def check():
    for i in range(n):
        start = i
        for j in range(h):
            if ladder[j][start]:
                start += 1
            elif start > 0 and ladder[j][start - 1]:
                start -= 1
        if i != start:
            return False
    return True

def solution(count, nh, nn):
    global result
    if check():
        result = min(result,count)
        return
    if count == 3 or result <= count:
        return
    for i in range(nh,h):
        if i == nh:
            tempN = nn
        else:
            tempN = 0
        for j in range(tempN,n - 1):
            if ladder[i][j] or ladder[i][j + 1]:
                continue
            if j >= 1 and ladder[i][j - 1]:
                continue
            ladder[i][j] = True
            solution(count + 1, i, j + 2)
            ladder[i][j] = False
solution(0,0,0)
if result >= 4:
    print(-1)
else:
    print(result)

 

 

_____________________________________________________________________________________________________

 

 

어려워