[BOJ/백준] 15684 사다리 조작

def check():
    global N,H
    for ind in range(N):
        current_ind = ind
        for k in range(H):
            if visited[k][current_ind]:
                current_ind += 1
            elif current_ind>0 and visited[k][current_ind-1]:
                current_ind -= 1
        if current_ind != ind:
            return False
            
    return True




def dfs(row_index,col_index,cnt,limit):
    global N,H,result
    if cnt > limit:
        return
    if check():
        result = min(cnt,result)
        return
    for k in range(row_index,H):
        if k == row_index:
            search_y = col_index
        else:
            search_y = 0
        for y in range(search_y,N-1):
            if not visited[k][y] and not visited[k][y+1]:
                visited[k][y] = 1
                dfs(k,y+2,cnt+1,limit)
                visited[k][y] = 0









N,M,H = map(int,input().split())
# H는 놓을 수 있는 개수
# M 은 가로선의 개수
# 앞은 가로선의 위치 뒤는 2개의 위치
result = float('inf')
visited = [[0]*N for _ in range(H)]
for _ in range(M):
    row,node = map(int,input().split())
    visited[row-1][node-1] = 1
if check():
    print(0)
else:
    for limit_insert_rows in range(1,4):
        dfs(0,0,0,limit_insert_rows)
        if result != float('inf'):
            print(result)
            break
    else:
        print(-1)

문제에서 최고로 놓을  수 있는 사다리의 개수는 3개가 최대이므로, 기본적으로 전체 사다리를 놓을 수 있는 위치를 골라서 재귀로 푸는 방식으로 해줬다. 그리고 result값이 바뀌면 break로 탈출을 해줬다. 

사다리의 가로선의 정보를 node-1,node 둘 중 왼쪽인 node-1에 저장해줬다.

그리고 사다리가 놓을 수 없는 조건은 현재 위치인 [가로선][세로선] 과 [가로선][세로선+1] 위치에 전부 0이 존재하면 사다리를 놓을 수 있다고 가정했다. 그리고 난뒤 재귀함수에서 y축을 +2만큼 이동시켜줬다. 그 이유는 해당 가로선에서  내가 고른 세로선에서 사다리를 놓게 되면 세로선 과 세로선+1의 위치에는 사다리를 놓을 수 없다. 그러므로, y를 +2 해주었다.

 

그리고, 가로선 중에서 주어진 row_index가 같을때에만 그러고 그 다음 가로선부터는 전체 세로선에 대해서 탐색하면 된다.

 

이렇게 사다리를 추가해주면서, check()라는 함수를 통해, 문제에 주여진 조건인 start_index와 사다리를 통과하고 나온 index가 같은지 비교를 해줘서 True,False 값을 반환시켜주었다.

 

이렇게 풀었지만, 다른 사람들의 코드를 공부하고 더 나은 풀이로 나중에 고쳤다.

import sys
def check():
    global N,H
    for ind in range(N):
        current_ind = ind
        for k in range(H):
            current_ind += visited[k][current_ind]
        if current_ind != ind:
            return False
            
    return True




def dfs(ladder_index,cnt,limit):
    global N,H,result
    if limit == cnt:
        if check():
            result = limit
        return
    for ind in range(ladder_index,N*H):
        row_index = ind//N
        col_index = ind%N
        if col_index == N-1:
            continue
        if not visited[row_index][col_index] and not visited[row_index][col_index+1]:
            visited[row_index][col_index] = 1
            visited[row_index][col_index+1] = -1
            dfs(ind+2,cnt+1,limit)
            if result != 4:
                return
            visited[row_index][col_index] = 0
            visited[row_index][col_index+1] = 0





N,M,H = map(int,input().split())
# H는 놓을 수 있는 개수
# M 은 가로선의 개수
# 앞은 가로선의 위치 뒤는 2개의 위치
if M == 0:
    print(0)
else:
    result = 4
    call = 0
    visited = [[0]*N for _ in range(H)]
    for _ in range(M):
        row,node = map(int,sys.stdin.readline().split())
        visited[row-1][node-1] = 1
        visited[row-1][node] = -1

    if check():
        print(0)
    else:
        for k in range(1,4):
            dfs(0,0,k)
            if result != 4:
                break
        if result != 4:
            print(result)
        else:
            print(-1)

 기본적인 원리는 비슷하다. 하지만 몇몇 부분에서 백트래킹을 해줬다.

먼저 좌측에만 가로선의 정보를 저장했던 거에서, 좌우측에 정보를 저장해줬다. 대신 그 값을 1과 -1을 저장시켜줬다.

이전 코드에서 좌측에 있는지 우측에 있는지 판별해서 세로선의 index를 바꿔주던거에서 좀 더 깔끔하게 바꿔주었다.

 

그리고 매 함수마다 check를 해주던 것을 cnt == limit에 도달했을때, check를 해주었다.

또한 결과값의 기본값이 바뀌었을때 break를 해주는 곳을 여러군데 추가해줬다.

가장 크게 바뀐 것은 2중 for문을 돌리던 것을 단일 for문으로 바꿔주었다.

다음과 같이 세로선 8과 가로선 4일때를 그려보면 다음과 같이 사다리를 그릴수 있을 것이다.

 

여기서 각각의 교차선을 구한다고 생각하면,

 

다음과 같이 세로선 8* 가로선 4 만큼의 교차선이 나올 수 있다. 그러므로 문제에 주어진 N*H 만큼의 교차선이 주어질 수 있다.

 

이 중에서 사다리를 놓을 수 있는 교차선은 빨간색 동그라미가 쳐진 교차선 뿐이다. N번 세로선인 8번 세로선에는 그 다음 세로선이 없기 때문에 사다리를 놓을 수 없다.

 

그 외의 나머지 부분 교차선에 사다리를 놓는다고 생각하고 재귀함수를 돌리면 된다. 위에서 설명 했듯이 한 곳에 사다리를 놓을시, 해당 교차선 위치에서 가로로 2칸만큼 더 가야지만 사다리를 놓을 수 있다. 

 

    for ind in range(ladder_index,N*H):
        row_index = ind//N
        col_index = ind%N
        if col_index == N-1:
            continue
        if not visited[row_index][col_index] and not visited[row_index][col_index+1]:
            visited[row_index][col_index] = 1
            visited[row_index][col_index+1] = -1
            dfs(ind+2,cnt+1,limit)
            if result != 4:
                return
            visited[row_index][col_index] = 0
            visited[row_index][col_index+1] = 0

함수에서 이부분이 교차선을 나타내고, 교차선의 가로선과 세로선을 찾아내서 세로선이 마지막 위치한 것이면 넘어가고, 

사다리를 놓을 수 있으면, 사다리를 놓은 뒤, 해당 index에서 +2를 해줘서 재귀함수를 해준다.

 

구현은 안했지만, 가능한 또 다른 방법은 사다리를 놓을 수 있는 교차선들을 전부 구해놓은 상태에서, 조합을 이용해 사다리를 1개 놓았을 때, 2개 놓았을 때, 3개 놓았을 때,를 구분하고, 고른 사다리가 문제가 없는지 판별해주고, 문제에 조여진 조건대로 시작 index와 도착 index를 같은지 판별하는 방법을 써도 될것 같다.

 

 

문제 자체는 어렵게 보이지 않았지만, 실제로 구현하는데에 어려운점이 많았고, 많이 틀렸던 문제였다.

중간중간 가능성이 없는것을 멈춰주고, 시간을 줄이는데 노력해야지 풀 수 있었던 힘들었던 문제였다.