[백준 15684번] 사다리 조작

15684번: 사다리 조작

n, m, h = map(int,input().split())

answer = 4

def check(): # i번에서 시작한 세로선이 i번에서 끝나는지 확인하는 함수
    
    for i in range(n):
        temp = i # 이동하는 세로선 위치
        for j in range(h):
            if ladder[j][temp] == 1: # 오른쪽이 1인 경우(오른쪽으로 가로선이 쳐져있는 경우)
                temp += 1
            elif temp > 0 and ladder[j][temp-1] == 1: # 왼쪽이 1인 경우(왼쪽으로 가로선이 쳐져있는 경우)                
                temp -= 1
        if temp != i:
            return False
    return True

def dfs(count,x,y):
    global answer
    
    if check(): # 현재 상태에서 각 출발점이 도착점으로 잘 도착하는지 확인
        answer = min(answer,count)
        return
    
    if count == 3 or answer <= count: # 도착점이 정상적이지 않으면
        # cnt 값이 3일 경우 그 다음 호출에서 cnt가 4가 되어 문제 조건 위반하므로 return
        # cnt 값이 ans 보다 크거나 같을 경우에는 그 다음 경우를 볼 필요가 없으므로 return
        return
    

    for i in range(x,h):
        if i == x: # 같은 세로줄 확인하면 y부터 확인. 세로줄 다르면 0부터 
            k = y
        else:
            k = 0

        for j in range(k,n-1):
            if ladder[i][j] == 0: # 0인 경우 가로줄 만들고, 연속된 가로선을 만들지 않기 위해 j + 2호출
                ladder[i][j] = 1
                dfs(count + 1, i, j + 2)
                ladder[i][j] = 0

ladder = [[0]*n for _ in range(h)]

for _ in range(m):
    a, b = map(int,input().split())
    ladder[a-1][b-1] = 1

dfs(0,0,0)

if answer <= 3:
    print(answer)
else:
    print(-1)

이번 문제는 세로선의 개수(n)와 가로선을 놓을 수 있는 위치의 개수(h)가 정해지고, 주어진 가로선 정보를 가지고 사다리 타기를 진행했을 때 시작했던 세로선으로 돌아오도록 사다리를 조작하는 문제이다.

 

2차원 배열과 DFS를 사용해서 문제를 푼다는 것까진 알았었는데, 가로선 정보를 어떻게 저장하고 이동시킬지 감이 잡히지 않아 다른 사람의 풀이를 참고하였다.

 

가장 중요한 점은 추가해야 하는 가로선의 최솟값을 구하려면 결국 모든 경우의 수를 다 계산해보아야 하는 완전 탐색(Brute-Force)문제 라는 것이다.

 

따라서 i번 세로선에서 시작하여 i번에서 끝나는지 체크해주는 함수(check)를 선언하고, dfs와 backtracking을 사용하여 모든 경우의 수를 계산하였다.

 

(참고로 python3로는 시간초과가 발생하고, pypy3는 시간초과가 발생하지 않는데 삼성 기출문제는 대부분 pypy3로만 풀린다고 한다.. 🤔)

 

배운 점 및 느낀 점

1. 시간 제한이 여유가 있고, 최적의 값을 찾기 위한 아이디어가 잘 떠오르지 않는다면 완전탐색(Brute-Force) 알고리즘을 사용하자.
2. 문제에서 주어진 명세를 로직별로 구분하여 함수로 만드는 연습을 하자.
3. 로직이 잘 떠오르지 않더라도 일단 도전해보는 습관을 기르자.