[백트래킹 / 파이썬] 백준 15684번 : 사다리 조작 / 골드 4

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

15684번: 사다리 조작

사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선

www.acmicpc.net

처음엔 헉..하고 당황했으나 역시 차근차근 생각하면 실마리가 풀린다.

백트래킹으로 접근했고,

필요한 사다리의 최소 개수를 찾으라는 것에서 약간 멈칫한 이유는

백트래킹은 기본적으로 dfs로 탐색이 이루어지는데 최소 개수면 bfs로 해야 하나? 라는 생각이 들었기 때문이다.

하지만 사다리 개수는 while문을 통해 제어를 해주면 되고, 그 정해진 사다리 개수 내에서

원래 하던대로 dfs로 백트래킹을 해주면 됐었다.

<정답 코드 1>

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

table = [['N' for _ in range(n)] for _ in range(h)]

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

def dfs(count, limit):
    if count == limit:

        # simulation
        find = True
        for start in range(n):
            i = start
            for j in range(h):
                if table[j][i] == 'N':
                    continue
                elif table[j][i] == 'R':
                    i += 1
                elif table[j][i] == 'L':
                    i -= 1

            if i != start: # fail
                find = False
                break

        if find:
            return True
        else:
            return False

    for i in range(h):
        for j in range(n-1):
            if table[i][j] == 'N' and table[i][j+1] == 'N':

                table[i][j] = 'R'
                table[i][j+1] = 'L'

                if dfs(count + 1, limit):
                    return True

                #back-tracking
                table[i][j] = 'N'
                table[i][j+1] = 'N'

    return False

answer = 0
while answer < 4:

    # put the bridge
    if dfs(0, answer):
        print(answer)
        quit()

    answer += 1


# impossible
print(-1)

문제는 통과했으나 성능이 너무 안나오는 것 같아서 조금 생각을 해봤더니

사다리 놓을 위치를 정하는 과정에서 겹치는 상황이 많이 발생하였다.

for문을 돌다가 빈 자리에 사다리를 놓고 dfs로 한단계 깊숙이 들어가면, 다시 처음부터 for문을 돌며 빈 자리를 찾기 때문이었다.

이를 막기 위해 현재 위치 정보를 내려보내 주어 탐색 범위를 줄였다.

* 이때 조심할 건 x, y 위치 정보를 다 내려줘버리면 탐색 범위가 x, y 한번에 줄어들어 누락되는 위치가 생겨버림

<개선 코드>

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

table = [['N' for _ in range(n)] for _ in range(h)]

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

def dfs(count, limit, x):
    if count == limit:

        # simulation
        find = True
        for start in range(n):
            i = start
            for j in range(h):
                if table[j][i] == 'N':
                    continue
                elif table[j][i] == 'R':
                    i += 1
                elif table[j][i] == 'L':
                    i -= 1

            if i != start: # fail
                find = False
                break

        if find:
            return True
        else:
            return False

    for i in range(x, h):
        for j in range(n-1):
            if table[i][j] == 'N' and table[i][j+1] == 'N':

                table[i][j] = 'R'
                table[i][j+1] = 'L'

                if dfs(count + 1, limit, i):
                    return True

                #back-tracking
                table[i][j] = 'N'
                table[i][j+1] = 'N'

    return False

answer = 0
while answer < 4:

    # put the bridge
    if dfs(0, answer, 0):
        print(answer)
        quit()

    answer += 1


# impossible
print(-1)

dfs의 파라미터 1개만 추가시켜줬을 뿐인데 문제 성공 시간이 1/4로 줄어들었다.