[백준 15684번] 사다리 조작 - Python으로 구현하기

[백준 15684번] 사다리 조작 - Python으로 구현하기

 

문제 접근

• 주어진 사다리를 자료구조로 어떻게 표현해야 될지? 어떤 규칙이 있는지? 하나의 라인을 따라가보며 확인
• 내가 생각한 사다리 자료구조는 배열이다.
• itertools 의 product로 모든 인덱스 경우의 수를 구하고, combinations 로 조합을 뽑은 뒤 완전탐색을 해보자

[사다리 자료구조]

위 예시 사다리를 행렬로 표현해보면, 아래와 같다.(행은 가로선을 놓을 수 있는 곳, 열은 출발 라인번호)

	1	2	3	4
1	1	0	0	0
2	0	0	1	0
3	0	1	0	0
4	0	0	0	0
5	1	0	0	1
6	0	0	0	0

 

array[1][1]은 1번->2번 가로선이 1번 가로선 놓을수 있는 곳에 위치해 있음을 뜻한다.

반복문으로 각 열마다 어떤 위치로 가는지 확인하여 i열이 i열로 끝나지 않으면 continue 하고, 다음 경우의수를 확인한다.

어떤 위치로 가는지 확인 하는 구체적인 방법은 아래 코드에서 확인!

 

생각해볼 점

• 사다리 타기에 대한 로직을 한번 생각해 볼 수 있는 문제
• product 모듈 안쓰고 인덱스 모든 경우의 수 찾기?(modular로 가능)
• 최적화 고려해보기.

 

오답 분석

• 시간초과가 많이 나는 문제이다.
• 내 실수 : 반복문 안에 copy 모듈을 사용하여 처리를 깔끔하게 하려고 했으나, deepcopy의 시간복잡도가 O(n^2) 인것을 간과했다. 주의!!

 

* 2019-10-18 기준 백준 pypy3 채점서버에서 exit(0)을 런타임 에러로 인식하는 오류 있음.

from itertools import product,combinations as cm

def chk_sadari(sa,sa_added):
    for col in range(1,n+1):
        go = col
        for row in range(1,h+1):
            if sa[row][go]==1 or sa_added[row][go]==1:
                go+=1
            elif sa[row][go-1]==1 or sa_added[row][go-1]==1:
                go-=1
        if go != col:
            return False
    return True

n,m,h=map(int,input().split())
sadari = [[0]*(n+1) for _ in range(h+1)]    # 1 index

# 가로선이 없는 경우 예외처리
if m==0:
    print(0)
    exit(1)

# 사다리 입력정보
for _ in range(m):
    a,b=map(int,input().split())
    sadari[a][b]=1

if chk_sadari(sadari,sadari):
    print(0)
    exit(1)

for i in range(1,3+1):
    for now_line_list in cm(product(range(1,h+1),range(1,n)),i):  # 행렬의 인덱스를 1~h개를 뽑는 조합
        sadari_added = [[0]*(n+1) for _ in range(h+1)]
        # 뽑은 조합들로 사다리에 가로선 추가하기
        flag = False
        for pos in now_line_list:
            x,y=pos
            if sadari[x][y-1]==1 or sadari_added[x][y-1]==1 or sadari[x][y+1]==1 or sadari_added[x][y+1]==1 or sadari[x][y]==1:
                flag=False
                break
            sadari_added[x][y]=1
            flag= True
        if flag and chk_sadari(sadari,sadari_added):
            print(i)
            exit(1)
print(-1)

 

* 틀린 부분이나 더 나은 방법이 있을 수 있습니다. 지적해주시면 감사하겠습니다!!