백준 사다리 조작(Python)

문제 링크: www.acmicpc.net/problem/15684

15684번: 사다리 조작

삼성 기출문제로 상당히 까다로운 문제입니다. 우선 사다리는 2차원 배열을 통해 만들 수 있습니다.

input으로 n, m, h가 주어지는데 이때 사다리는 n과 h로 만들어야 하는 것에 주의해야 합니다.

이후 주어지는 가로선들은 2차원 배열에 1로 표시합니다. (예를 들어 1번째 줄 3과 4를 잇는 가로선은 graph[1][3]에만 1로 체크해두고 나중에 사다리를 내려오면서 왼쪽에도 가로선이 있는지 체크해보는 방식으로 구현하면 됩니다.)

새로운 사다리는 dfs+조합으로 사다리를 하나 놓을때마다 조건에 만족하는지 확인해보면 됩니다. (새로운 사다리를 놓을때 놓으려는 곳 양 옆쪽에 이미 사다리가 있는지도 체크해봐야합니다.)

dfs로 조합구현시에 인자로 start_index를 추가하는 것을 잊지말아야합니다. (잘못구현시 조합이 아닌 순열로 구현이되어 시간초과가 발생합니다.)

import sys
 
 
def check():
    for i in range(1, n+1):
        cur = i
        for j in range(1, h+1):
            if graph[j][cur] == 1:  # 여기서 graph[j][i]가 아니라 i 대신 cur을 넣어야 함
                cur += 1
            elif graph[j][cur-1] == 1:
                cur -= 1
 
        if cur != i:
            return False
 
    return True
 
 
def can_install(x, y):  # 새로 놓은 사다리가 양 옆과 인접하는지 체크
    if y == n:  # 맨 끝에는 사다리를 놓으면 안됨 (맨 끝과 연결하는 사다리는 맨 끝 - 1 번에 놓음)
        return False
 
    if y == 1:
        if graph[x][y+1] == 1:
            return False
    else:
        if graph[x][y+1] == 1 or graph[x][y-1] == 1:
            return False
 
    return True
 
 
def dfs(lv, start_idx):  # 조합 구하기
    global answer
 
    if lv > 3 or lv > answer:  # 예를들어 answer가 1이라면 사다리 2개 놓는 경우는 생략
        return
 
    if check():
        answer = min(answer, lv)
 
    for i in range(start_idx, h+1):
        for j in range(1, n+1):
            if graph[i][j] == 1:
                continue
            if can_install(i, j):
                graph[i][j] = 1
                dfs(lv+1, i)
                graph[i][j] = 0
 
 
# 세로, 가로
n, m, h = map(int, input().split())
if m == 0:
    print(0)
    sys.exit(0)  # 아래코드 실행안되게 종료
 
graph = [[0]*(n+1) for _ in range(h+1)]  # 사다리
for _ in range(m):
    a, b = map(int, input().split())
    graph[a][b] = 1
 
answer = 4
dfs(0, 1)  # 사다리를 인덱스 1부터 시작하게 만들었으므로
 
if answer == 4:
    print(-1)
else:
    print(answer)

 

pypy3으로 채점해보면 3916ms나 나오게 되네요.