시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	512 MB	64101	17087	8265	21.694%

문제

사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖는다. 아래 그림은 N = 5, H = 6 인 경우의 그림이고, 가로선은 없다.

초록선은 세로선을 나타내고, 초록선과 점선이 교차하는 점은 가로선을 놓을 수 있는 점이다. 가로선은 인접한 두 세로선을 연결해야 한다. 단, 두 가로선이 연속하거나 서로 접하면 안 된다. 또, 가로선은 점선 위에 있어야 한다.

위의 그림에는 가로선이 총 5개 있다. 가로선은 위의 그림과 같이 인접한 두 세로선을 연결해야 하고, 가로선을 놓을 수 있는 위치를 연결해야 한다.

사다리 게임은 각각의 세로선마다 게임을 진행하고, 세로선의 가장 위에서부터 아래 방향으로 내려가야 한다. 이때, 가로선을 만나면 가로선을 이용해 옆 세로선으로 이동한 다음, 이동한 세로선에서 아래 방향으로 이동해야 한다.

위의 그림에서 1번은 3번으로, 2번은 2번으로, 3번은 5번으로, 4번은 1번으로, 5번은 4번으로 도착하게 된다. 아래 두 그림은 1번과 2번이 어떻게 이동했는지 나타내는 그림이다.

1번 세로선	2번 세로선

사다리에 가로선을 추가해서, 사다리 게임의 결과를 조작하려고 한다. 이때, i번 세로선의 결과가 i번이 나와야 한다. 그렇게 하기 위해서 추가해야 하는 가로선 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 세로선의 개수 N, 가로선의 개수 M, 세로선마다 가로선을 놓을 수 있는 위치의 개수 H가 주어진다. (2 ≤ N ≤ 10, 1 ≤ H ≤ 30, 0 ≤ M ≤ (N-1)×H)

둘째 줄부터 M개의 줄에는 가로선의 정보가 한 줄에 하나씩 주어진다.

가로선의 정보는 두 정수 a과 b로 나타낸다. (1 ≤ a ≤ H, 1 ≤ b ≤ N-1) b번 세로선과 b+1번 세로선을 a번 점선 위치에서 연결했다는 의미이다.

가장 위에 있는 점선의 번호는 1번이고, 아래로 내려갈 때마다 1이 증가한다. 세로선은 가장 왼쪽에 있는 것의 번호가 1번이고, 오른쪽으로 갈 때마다 1이 증가한다.

입력으로 주어지는 가로선이 서로 연속하는 경우는 없다.

출력

i번 세로선의 결과가 i번이 나오도록 사다리 게임을 조작하려면, 추가해야 하는 가로선 개수의 최솟값을 출력한다. 만약, 정답이 3보다 큰 값이면 -1을 출력한다. 또, 불가능한 경우에도 -1을 출력한다.

정답 - Python

import sys
from itertools import combinations

n, m, h = map(int, sys.stdin.readline().rstrip().split())
ladder = [[False for _ in range(n)] for __ in range(h)]
for _ in range(m):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    ladder[a - 1][b - 1] = True


def go_down():
    for cur in range(n):
        pos = cur
        for i in range(h):
            if ladder[i][pos]:
                if pos == n - 1:
                    pos -= 1
                else:
                    pos += 1
            elif pos > 0 and ladder[i][pos - 1]:
                pos -= 1
        if pos != cur:
            return False
    return True


if go_down():
    print(0)
    exit(0)
else:
    ans = 1
    while ans < 4:
        for c in combinations(range(n * h), ans):
            tmp = []
            is_go = True
            for num in c:
                x, y = num % n, num // n
                if ladder[y][x] or (x < n - 1 and ladder[y][x + 1]):
                    is_go = False
                    continue
                tmp.append([x, y])

            if is_go:
                for x, y in tmp:
                    ladder[y][x] = True
                if go_down():
                    print(ans)
                    exit(0)
                for x, y in tmp:
                    ladder[y][x] = False
        ans += 1
print(-1)

결과

풀이

가지치기로 경우의 수를 최대한 줄여서 풀어야 하는 문제였습니다.
저는 이 문제를 풀면서 총 2번의 고비를 맞았었습니다.
1. 사다리 게임을 어떻게 코드로 옮기지?
2. 시간 초과에 걸리는데 시간을 어떻게 줄이지?

1. 사다리 게임을 어떻게 코드로 옮겨서 풀지?

처음 문제를 보고 조금 당황했습니다. 사다리 게임은 평소에 많이 경험해 봐서 익숙한데 이를 어떻게 옮겨야 하는지 몰랐거든요.
하지만 생각을 해 보니 2차원 배열을 순회하면서 내려가는 것을 구현하고, visited 배열을 이용해 x좌표를 옮겨주면 되겠다! 라는 발상을 하니 코드로 옮기는 것은 그렇게 어렵지는 않았습니다.

그리고 삼성 코테 문제가 언제나 그렇듯 시나리오는 짜서 문제를 풀어봤습니다.
1. 현재 사다리 상태를 ladder 배열에 저장한다
2. 현재 사다리 상태에서 i -> i로 모두 가면 사다리를 놓을 필요가 없다 -> 0 출력
3. 이외의 상황일때, 사다리를 모든 자리에 1, 2, 3개씩 선택해서 사다리를 놓아 본 다음 정답이 맞는지 확인한다
- 단 선택한 자리 중 하나라도 초기 상태의 사다리와 겹치는 경우는 무시한다
- 또, 선택한 자리 중 하나라도 조건에 위배되어 사다리를 못 놓는 경우 또한 무시한다.

3번의 1, 2, 3개씩 선택하는 경우의 수는 itertools의 combinations를 사용해 조합을 사용했습니다.

go_down()

사다리가 결정된 다음 현재 상태의 사다리가 문제의 조건을 만족하는지 확인하는 함수입니다.
이 함수를 처음 작성할 당시에는 다음과 같았습니다.

def go_down():
    pt = 0
    for cur in range(n):
        pos = cur
        for i in range(h):
            if ladder[i][pos]:
                if pos == n - 1:
                    pos -= 1
                else:
                    pos += 1
            elif pos > 0 and ladder[i][pos - 1]:
                pos -= 1
        if pos == cur:
            pt += 1
    return pt == n

혹시 뭐가 문제인지 보이시나요?
바로 가지치기를 안했다 입니다...

위 함수는 i -> i로 가지 않는지 모두를 확인합니다. 하지만 이는 매우 비효율적이죠
하나만 i -> i로 가지 않더라도 False를 리턴하면 되는데 말이죠!!!
그래서 아래와 같이 수정했습니다!!

def go_down():
    for cur in range(n):
        pos = cur
        for i in range(h):
            if ladder[i][pos]:
                if pos == n - 1:
                    pos -= 1
                else:
                    pos += 1
            elif pos > 0 and ladder[i][pos - 1]:
                pos -= 1
        if pos != cur:
            return False
    return True

이렇게 수정하니깐 귀신같이 통과하더라고요.

시간 복잡도 이외에는 예외처리 정도만 신경쓰면 금방푸는 문제입니다.