[백준] 15684 : 사다리 조작 (삼성 SW 역량 테스트) / python

1. 문제 설명

15684번: 사다리 조작

 

입력

N → 세로선의 갯수 (2 ≤ N ≤ 10)

M → 가로선의 갯수 (0 ≤ M ≤ (N-1)×H)

H → 세로선마다 가로선을 놓을 수 있는 위치의 갯수 (1 ≤ H ≤ 30)

lines → 가로선의 정보 → (a, b) X M개 (1 ≤ a ≤ H, 1 ≤ b ≤ N-1) b번 세로선과 b+1번 세로선을 a번 점선 위치에서 연결

 

제한조건

두 가로선이 연속하거나 접하면 안된다.

 

구하고자 하는 바

사다리에 가로선을 추가해서 i번 세로선의 결과가 i번이 나올 수 있도록 추가해야하는 가로선 개수의 최솟값

단, 추가해야할 가로선이 3을 넘어가거나, 불가능한 경우는 -1을 출력한다.

 

2. 풀이 전 계획과 생각

행위의 규칙성, 패턴 파악

가로선을 추가하는 모든 경우를 구해주고

그에 따른 세로선의 결과가 i번이 나오는지 확인하자.

가로선을 추가하는 모든 경우를 구한다면,

• H * (N - 1) = 10 * 30 → 2 ^ 300 ⏰
• 제한조건이 있다. 추가해야할 가로선이 3을 초과하면 종료한다는 가지치기를 해주자.

 

필요한 로직

• 가로선을 추가하는 모든 경우를 구하는 함수
  • 제한 조건 : 두 가로선이 연속하거나 서로 접하면 안된다.
  • 종료 조건 : 300개를 다 봤다면, 종료
  • 가지치기 조건 : 추가해야할 가로선이 3을 초과하면 종료한다.
• 세로선의 결과를 알려주는 함수
• 각 세로선의 결과 모두가 자기자신인지 확인해주는 함수

 

자세히

• 가로선을 추가하는 모든 경우를 구하는 함수
  • 제한 조건 : 두 가로선이 연속하거나 서로 접하면 안된다.
  • 종료 조건 : 300개를 다 봤다면, 종료
  • 가지치기 조건 : 추가해야할 가로선이 3을 초과하면 종료한다.
  1. 둘 수 있다면 두는 경우와 놔두고 원래대로 복구
  2. 그외는 안두는 경우로 가기
• 세로선의 결과를 알려주는 함수
  • 세로선을 가지고, i ↔ i +1 변경하기
• 각 세로선의 결과 모두가 자기자신인지 확인해주는 함수
• 가로선을 놔둘 수 있는지 체크하는 함수
• 두 가로선이 연속하는지 체크하는 함수

 

3. 풀이

MAX_INT = 4

N, M, H = tuple(map(int, input().split()))
pre_lines = [tuple(map(int, input().split())) for _ in range(M)]
total_lines = [[0] * (N + 1) for i in range(H + 1)]
for line in pre_lines:
    a, b = line
    total_lines[a][b] = 1

def idx_to_coordinate(current_idx):
    y, x = current_idx // (N - 1) + 1, current_idx % (N - 1) + 1
    return y, x

def is_all_itself():
    expected_result = [num for num in range(0, N)]
    result = [num for num in range(0, N)]
    for y in range(1, H + 1):
        for x in range(1, N + 1):
            if total_lines[y][x] == 1:
                result[x - 1], result[x] = result[x], result[x - 1]

    return result == expected_result

def is_continuous(y, x):
    return total_lines[y][x + 1] == 1 and total_lines[y][x - 1] == 1

def can_put(current_idx):
    y, x = idx_to_coordinate(current_idx)
    return total_lines[y][x] != 1 and not is_continuous(y, x)

def combination(current_idx, count):
    global answer, total_lines
    if count >= MAX_INT or count > M:
        return

    if is_all_itself():
        answer = min(answer, count)
        return
    
    if current_idx == (N - 1) * H:    
        return

    y, x = idx_to_coordinate(current_idx)

    combination(current_idx + 1, count)

    if can_put(current_idx):
        total_lines[y][x] = 1
        combination(current_idx + 1, count + 1)
        total_lines[y][x] = 0

answer = MAX_INT
combination(0, 0)

if answer == MAX_INT:
    print(-1)
else:
    print(answer)

 

문제점

시간 초과 발생

 

4. 풀이하면서 막혔던 점과 고민

🤔 여기서 어떻게 더 시간을 줄여줄 수 있을까?

이미 갱신된 값보다 크면 확인해줄 필요가 없기에 가지치기 조건을 추가해주자.

if count >= answer or count > M:
	return

→ 시간 초과

더 줄여보자. 연속된 가로선이 나올 수 없는 곳에만 검사하자.

def combination(current_idx, count):
    global answer, total_lines
    if count >= answer or count > M:
        return

    if is_all_itself():
        answer = min(answer, count)
        return

    for candidate_idx in range(current_idx, len(candidate)):
        y, x = candidate[candidate_idx]
        if not is_continuous(y, x):
            total_lines[y][x] = 1
            combination(candidate_idx + 1, count + 1)
            total_lines[y][x] = 0

candidate = []
for i in range(1, H + 1):
    for j in range(1, N):
        if not is_continuous(i, j) and not total_lines[i][j]:
            candidate.append((i, j))

 

5. 2차 풀이

MAX_INT = 4
N, M, H = tuple(map(int, input().split()))
pre_lines = [tuple(map(int, input().split())) for _ in range(M)]
total_lines = [[0] * (N + 1) for _ in range(H + 1)]
for line in pre_lines:
    a, b = line
    total_lines[a][b] = 1

def is_all_itself():
    for x in range(1, N + 1):
        current_x = x
        for y in range(1, H + 1):
            if total_lines[y][current_x - 1] == 1:
                current_x -= 1
            elif total_lines[y][current_x] == 1:
                current_x += 1

        if current_x != x:
            return False

    return True

def is_continuous(y, x):
    return total_lines[y][x + 1] == 1 or total_lines[y][x - 1] == 1

def combination(current_idx, count):
    global answer, total_lines
    if count >= answer or count > M:
        return

    if is_all_itself():
        answer = min(answer, count)
        return

    for candidate_idx in range(current_idx, len(candidate)):
        y, x = candidate[candidate_idx]
        if not is_continuous(y, x):
            total_lines[y][x] = 1
            combination(candidate_idx + 1, count + 1)
            total_lines[y][x] = 0

candidate = []
for i in range(1, H + 1):
    for j in range(1, N):
        if not is_continuous(i, j) and not total_lines[i][j]:
            candidate.append((i, j))

answer = MAX_INT
combination(0, 0)

if answer == MAX_INT:
    print(-1)
else:
    print(answer)

 

6. 풀이 후 알게된 개념과 소감

• 모든 경우를 따질 때, 시간복잡도를 낮추기 위해서는 가지치기할 것이 무엇이 있는지 확인할 수도 있지만,
  애초에 탐색할 때 필요한 부분만 탐색하는 방법도 있다.
  • 위의 문제에서 필요한 부분만 탐색하는 경우는 연속하지 않는 곳의 후보에만 탐색하는 것이다.