백준 15684 사다리조작 (python)

존버는 승리한다

 

질문은 여기!

15684번: 사다리 조작

76%에서 7번 틀려서 백준님 찾아갈까 생각했는데 30분만 좀 쉬고 오자 하고 쉬고 와서 보니까 역시 초기화가 잘못되어있었다 

이 문제는 9% 시간초과 - 백트래킹

11% - 사다리 놓기 설정 잘못

70%대 - 초기화 문제

라는 글을 봐서 

계속 몇번을 봐도 괜찮았던 것 같은데 너무 어이없는 곳에서 틀리고 있었던 것.. 

그래도 한시간 내에 찾아내서 다행이다. 

 

아이디어

1. 이차원 배열로 사다리를 구현! n과 n+1 사이에 j번째 줄에 (0부터 시작했을 때) 선이 있는 경우 arr[j][n] 를 1로 처리해준다.

2. 0부터 3까지 추가로 사다리가 가능한 숫자를 bfs로 탐색! 중간에 답이 나오면 바로 끝낼 수 있게(for 문 이용)

3. 각각 사다리 추가할 장소는 dfs로 구현했다. (재귀함수)

4. 추가가 끝났으면 사다리를 내려보는 검증 함수를 이용해 true 가 나오면 min_val을 추가한 사다리 개수로 바꿔주고 끝!

 

 

 

 

코드

"""
백준 15684 사다리조작 python
https://www.acmicpc.net/problem/15684
Code by jungwonkkim
"""

def down(): #사다리 조건 확인 함수
    for i in range(N):
        s = i
        j = 0
        while j < H:
            if ladder[j][s]:
                s += 1
                j += 1
            elif s > 0 and ladder[j][s-1]:
                s -= 1
                j += 1
            else:
                j += 1
        if s == i:
            continue
        else:
            return False
    return True


def dfs(chance, x, y):
    global min_val
    global ladder
    if min_val != -1: #이미 답 나왔을경우 더이상의 탐색 의미 없음
        return
    if chance == 0: #더이상 넣을 수 있는 기회가 없을 경우
        if down(): #사다리 내리는 함수 진행후 만약 모든 i 번째 세로줄의 결승점이 i번째 일 경우
            min_val = cnt #min_val 값 cnt 로 고쳐준 후 함수 리턴
        return
    for dx in range(x, H):
        for dy in range(N-1):
            if dx == x and dy <= y: #이전에 탐색 완료
                continue
            if dy > 0 and ladder[dx][dy-1]: #왼쪽에 선이 있는 경우
                continue
            if ladder[dx][dy] or ladder[dx][dy+1]: #해당 장소 혹은 오른쪽에 선이 있는 경우
                continue
            ladder[dx][dy] = 1
            dfs(chance-1, dx, dy)
            ladder[dx][dy] = 0


N, M, H = map(int, input().split())
ladder = [[0 for _ in range(N)] for _ in range(H)] #가로 N이고 세로 H인 사다리 만들기
min_val = -1
for _ in range(M):
    a, b = map(int, input().split())
    ladder[a-1][b-1] = 1 #ladder[x][y] 가 1이라면 y번째와 y+1번째의 세로선이 x+1번째 가로선에서 이어져 있다는 뜻
for cnt in range(4):
    dfs(cnt, 0, -1) #cnt: 새로운 라인의 개수, 백트래킹을 위한 x,y좌표
    if min_val == -1: #그 전에서 아직 답이 나오지 않은 경우는 가능한 라인 개수를 늘린다.
        continue
    else:
        break
print(min_val)