(Python) 백준 15684번: 사다리 조작

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

15684번: 사다리 조작

• 알고리즘 분류:
  
  • 브루트 포스

---

Python으로 제출했으나 시간초과.

PyPy3로 제출해서 통과

 

이 문제는 시간 단축을 위해 고민을 좀 더 해봐야될 것 같다.

 

어떤 문제들을 풀던지 간에, combinations를 사용해서 조합을 만들면 항상 시간이 많이 걸리는 것 같다.

삼성에서는 combinations를 import하지 못하도록 막을 수 있으니

순열, 조합, 중복 순열, 중복 조합, 집합의 모든 경우의 수 등을 직접 구현해볼 수 있으면 좋겠다.

+ 제너레이터에 대한 개념도 익혀두면 좋을 것 같다.

 

from itertools import combinations
 
 
## 하나라도 다른곳에 수렴할 경우 False, 아니면 True 반환
def fall():
    for y in range(1, 1 + N):
        i = 0  # x좌표 초기값
        j = y  # y좌표 초기값
        while i != H + 1:                 # 맨 밑에 도착할때까지 반복
            if alist[i + 1][j - 1] == 1:  # 왼쪽에 사다리가 있다면
                i, j = i + 1, j - 1       # 왼쪽으로 이동
            elif alist[i + 1][j] == 1:    # 오른쪽으로 가는 사다리가 있다면
                i, j = i + 1, j + 1       # 오른쪽으로 이동
            else:                         # 사다리가 없다면
                i = i + 1                 # 아래로 이동
        if j != y:                        # 본래 위치에 도달하지 못했다면
            return False                  # False
    return True                           # 모두 본래 위치에 도달했으므로 True
 
 
## a좌표와 b좌표에 사다리를 놓았을 경우 서로 인접하는지 아닌지 알아보는 함수이다.
def check(a, b):
    if a[0] != b[0]:
        return True
    elif abs(a[1] - b[1]) == 1:
        return False
    else:
        return True
 
 
def fn():
    if fall(): return 0     # 사다리를 놓지 않았으나 자기 짝을 찾아가는 경우
    
    for sadari in addlist:  # 사다리를 하나만 놓았을 경우
        alist[sadari[0]][sadari[1]] = 1
        if fall():
            return 1
        else:
            alist[sadari[0]][sadari[1]] = 0
    
    for sadari in combinations(addlist, 2):           # 사다리를 두개 놓았다면
        if not check(sadari[0], sadari[1]): continue  # 새로 놓으려고 하는 두개의 사다리가 양옆으로 인접할경우
        alist[sadari[0][0]][sadari[0][1]] = 1         # 첫번째 사다리를 놓아준다.
        alist[sadari[1][0]][sadari[1][1]] = 1         # 두번째 사다리를 놓아준다.
        if fall(): return 2                           # 자기 자리로 수렴하는지 확인한다.
        alist[sadari[0][0]][sadari[0][1]] = 0         # 첫번째 사다리 해제
        alist[sadari[1][0]][sadari[1][1]] = 0         # 두번째 사다리 해제
 
    for sadari in combinations(addlist, 3):     # 사다리를 3개 놓는다면
        if not (check(sadari[0], sadari[1]) and check(sadari[0], sadari[2]) and check(sadari[1], sadari[2])): continue
        alist[sadari[0][0]][sadari[0][1]] = 1   # 첫번째 사다리 놓아준다.
        alist[sadari[1][0]][sadari[1][1]] = 1   # 두번째 사다리 놓아준다.
        alist[sadari[2][0]][sadari[2][1]] = 1   # 세번째 사다리 놓아준다.
        if fall(): return 3                     # 자기 자리로 수렴하는지 확인한다.
        alist[sadari[0][0]][sadari[0][1]] = 0   # 첫번째 사다리 해제
        alist[sadari[1][0]][sadari[1][1]] = 0   # 두번째 사다리 해제
        alist[sadari[2][0]][sadari[2][1]] = 0   # 세번째 사다리 해제
    ## 사다리를 3개까지 놓아봤음에도 return하지 않았다면 -1을 return한다.
    return -1
 
 
if __name__ == '__main__':
    ## 세로개수(N), 사다리개수(M), 가로개수(H)
    N, M, H = map(int, input().split())
    alist = [[0] * (N + 2) for _ in range(H + 2)]
    for i in range(M):
        a, b = map(int, input().split())
        alist[a][b] = 1
 
    addlist = []  # 사다리를 놓을 수 있는 위치
    for i in range(1, 1 + H):
        for j in range(1, N):
            if not (alist[i][j - 1] or alist[i][j] or alist[i][j + 1]):
                addlist.append([i, j])
    print(fn())