[삼성SW역량][Python/BOJ] 백준 15684 사다리조작(dfs)

🐾 20220918

 

 

사다리를 어떻게 생각해야할지 생각이 많았는데

지금으로서는 이렇게 생각하는게 제일 쉽다. (아래 사진 참고)

 

 

 

 

선을 그을수 있는 candidate를 만든다.

candidate를 돌면서 그을수  있다면 그으면서 가장 최소의 check가 True인 값을 구한다.

 

 

 

코드 : 

 

def check() : # i 번 세로선의 결과가 i가 나오는지 확인  
    for i in range(1,n+1) : # 세로선을 돌면서 
        k = i
        for j in range(1,h+1) : # 선을 놓을 수 있는 곳을 확인 
            if line[j][k] == 1 :
                k+=1 
            elif line[j][k-1] == 1 : 
                k-=1 
        if i != k : return False 
    return True 


# added : 그어진 선 개수, num : candidate에서 이용한 번호 
def solve(added, num) : 
    global ans 
    # 그어진 선의 개수가 ans보다 많다면 
    if added >= ans : return  
    if check() : 
        ans = min(ans,added)
        return
    # 3개 그엇는데 check가 통과가 안되었다면 다음 호출에는 ans보다 크거나 같아질 것이므로
    if added ==3 : return   
    
    for idx in range(num+1, len(candidate)) :
        i,j  = candidate[idx]
        if line[i][j-1] ==0 and line[i][j+1] == 0:
            line[i][j] = 1 
            solve(added+1, idx)
            line[i][j] = 0 
           
if __name__=="__main__" :
    n,m,h = map(int,input().split())
    line = [[0]*(n+1) for i in range(h+1)]
    candidate = []
    
    for i in range(m) :
        a,b = map(int,input().split())
        line[a][b] = 1 
        
    # 선을 그을 수 있는 후보 찾기 
    for i in range(1,h+1) :
        for j in range(1,n) :
            if line[i][j] == 0 and line[i][j-1] ==0 and line[i][j+1] == 0 :
                candidate.append([i,j])
    ans = 4
    solve(0,-1)
    print(ans if ans < 4 else -1 )

 

 

 

 

 

---

 

20220918

 

복습을 하며 다시 풀어보았다. 

def check(mp) :
    for i in range(1,n+1) :
        cur = i
        for j in range(1,h+1) :
            if mp[j][cur] : cur+=1 
            elif mp[j][cur-1] : cur-=1 
        if cur != i : return False 
    return True 

def dfs(idx,mp) :
    global ans 
    if idx > 3 : return 
    if check(mp) :
        ans = min(ans,idx)
        return 
    if idx == 3 :return 
    if idx  > ans : return 
    else :
        for i in  range(1,h+1) :
            for j in range(1,n) :
                if mp[i][j] == 0 and mp[i][j-1] == 0 and mp[i][j+1] == 0:
                    mp[i][j] = 1 
                    dfs(idx+1, mp)
                    mp[i][j] = 0 
                    
        
if __name__=="__main__" :
    n,m,h = map(int,input().split())
    mp = [[0]*(n+1) for _ in range(h+1)]
    for i in range(m) :
        a,b = map(int,input().split())
        mp[a][b] = 1 
    ans = int(1e9)
    dfs(0,mp)
    
    if ans == int(1e9) : print(-1)
    else : print(ans)

 

candidate를 만들지 않고 dfs를 호출할 때마다 이중 for문을 도는 것으로 만들어보았다. 

AC는 했으나 시간이 굉장히 오래 걸렸다. 

 

 

 

candidate 가 없을 때 -> 6500 ms 

candidate 가 있을 때 -> 1052 ms 이다. 

 

 

 

candidate 아이디어를 잘 떠오르지 않았다. 

다음에는 떠올릴 수 있기를 !

 

+ dfs를 미리 끝낼 수 있도록 idx >3 : return 이라든지 이런 것들로 잘 끊어낼 수 있도록 하자.

 

 

 

candidate를 이용하도록 수정한 코드 : 

def check() :
    for i in range(1,n+1) :
        cur = i
        for j in range(1,h+1) :
            if mp[j][cur] : cur+=1 
            elif mp[j][cur-1] : cur-=1 
        if cur != i : return False 
    return True 

def dfs(idx,cnt) :
    global ans 
    if idx > 3 : return 
    if check() :
        ans = min(ans,idx)
        return 
    if idx == 3 :return 
    if idx  > ans : return 
    else :
        for added in range(cnt+1, len(candidate)) :
            i,j = candidate[added]
            if mp[i][j-1] == 0 and mp[i][j+1] == 0:
                    mp[i][j] = 1 
                    dfs(idx+1, added)
                    mp[i][j] = 0 
                    
        
if __name__=="__main__" :
    n,m,h = map(int,input().split())
    mp = [[0]*(n+1) for _ in range(h+1)]
    for i in range(m) :
        a,b = map(int,input().split())
        mp[a][b] = 1 
    ans = int(1e9)
    candidate = []
    for i in range(1,h+1) :
        for j in  range(1,n) :
            if mp[i][j] == 0 and mp[i][j-1] == 0 and mp[i][j+1] == 0:
                candidate.append([i,j]) 
    dfs(0,-1)
    
    if ans == int(1e9) : print(-1)
    else : print(ans)

 

 

 

참고 블로그 : 

 

https://ryu-e.tistory.com/69

[Python] 백준 15684 사다리 조작

 

https://rhdtka21.tistory.com/69