BOJ - 사다리 조작 15684번 (python)

❓ 문제 - 백준 사다리 조작 15684번 - python 풀이법

출처 

(https://www.acmicpc.net/problem/15684)

15684번: 사다리 조작

 

 

 

📝 문제해결법

1. 이 문제는 DFS+구현으로 풀었다.

• 일단 사다리가 이미 있는 곳은 visited 리스트를 통해 방문 처리 해준다.
• 주어진 문제에 조건에서 양 옆에 사다리가 있으면 사다리를 놓을 수 없기 때문에 사다리를 놓여질 수 있는 행과 열을 돌면서 양쪽과 해당 위치에 사다리가 없다면 사다리를 놓을 수 있는 후보군으로 두기 위해 combi 리스트에 해당 행과 열의 위치를 append 해준다.
• check() :  사다리가 놓여져 있을 때 , 모든 열에 대해서 현재 i번째 열이 사다리를 이동해서 i번째에 도착할 수 있는지 확인할 수 있도록 한다. 구현 방식은 해당 열에 대해서 왼쪽에 만약 사다리가 놓였다면 왼쪽으로 이동하므로 now(이동된 값)을 now-1로 해주고, 만약 현재 위치에 사다리가 놓였다면 오른쪽으로 이동해야하므로 now(이동된 값)을 now+1로 해준다. 마지막에 처음 출발했던 열의 번호와 now(이동된 값)을 비교해서 True, False를 반환한다.
• dfs() : 일단 4개 이상 사다리를 놓을 수 없기 때문에 사다리를 3번 이상 놓았을 때도 check() , 즉 모든 열의 값이 사다리를 타고 이동했을 때 자신의 열값과 이동된 값지 않다면 더이상 dfs 를 돌릴 필요 없기 때문에 return 해준다.
• dfs() : 사다리를 놓을 수 있는 후보군의 인덱스에 다시 한번 사다리를 놓을 수 있는지 확인하고 (전에 재귀함수를 통해 사다리를 놓은 후 현재 사다리를 놓을 수 없을 수도 있음), 사다리를 놓을 수 있다면 사다리를 놓은 후 dfs 함수로 재귀를 구현한다.

 

2. 문제 풀면서 얻은 교훈

• 사다리를 놓을 수 있을지 없을지 확인할 때 인덱스의 범위(맨 끝값)이 확인하기 힘들어서 구현이 이상한 방향으로 흘렀다. 이럴 땐, 인덱스를 접근하는 visited 리스트의 범위를 0~n+1 , 0 ~ h+1로 늘린다면 인덱스 범위 확인하는데 어려움 없이 해결할 수 있다.
• 처음 visited 함수를 해당 곳에 사다리를 놓았다고 가정하기 위해 사다리를 놓을 때마다 visited 함수를 copy해서 시간초과가 발생했다. 구현을 다른 방식으로 바꿔 (만약 사다리를 놓았을 때 방문처리 후 dfs 다 빠져나온 후 다시 False 처리 하도록) 해결하였다.

 

 

💻 소스코드

n, m, h = map(int, input().split())
visited = [[False] * (n+1) for _ in range(h+1)]
combi = []
for _ in range(m):
    a, b = map(int, input().split())
    visited[a][b] = True

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

def dfs(depth, idx):
    global answer
    if depth >= answer:
        return
    if check():
        answer = depth
        return

    for c in range(idx, len(combi)):
        x, y = combi[c]
        if not visited[x][y-1] and not visited[x][y+1]:
            visited[x][y] = True
            dfs(depth+1, c+1)
            visited[x][y] = False

for i in range(1,h+1):
    for j in range(1, n):
        if not visited[i][j-1] and not visited[i][j] and not visited[i][j+1]:
            combi.append([i, j])

answer = 4
dfs(0, 0)

print(answer if answer < 4 else -1)