백준 문제 중 2225번, 구현, ‘사디리조작’

백준 문제 중

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

문제

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

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

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

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

위의 그림에서 1번은 3번으로, 2번은 2번으로, 3번은 5번으로, 4번은 1번으로, 5번은 4번으로 도착하게 된다. 아래 두 그림은 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을 출력한다.

---

풀이

시간초과 때문에 상당히 오래 고민했던 문제이다. 사다리 타기를 하면서 조건을 만족하는지 확인하는 부분의 최적화가 중요했다.

코드의 흐름은 이렇다.

1. 사다리의 상태를 저장할 배열 ladders를 선언하고 주어진 정보에 맞게 최신화 한다.
2. 사다리를 놓을 수 있는 후보들을 체크해 candidates에 저장한다.
3. 문제의 조건인 사다리타기를 마치고 i번 사다리가 i번에 도착하는지 확인할 함수 ghost_leg_check() 를 선언한다.
4. dfs를 진행한다. candidates에 있는 후보들을 조합해서 하나씩 뽑아 사다리를 놓아보는 과정을 3개 이상 고를때 까지 진행한다.(참고로 dfs를 통한 조합은 N과 M 2에서 다루어 보았다.)

추가설명

• ladders에 사다리의 정보를 넣을 때 사다리 타기 게임의 특성을 조금 고려해보자.
  사다리 타기를 진행 할 때는 현재 사다리를 타고 내려가다가 오른쪽 가로로 이어진 사다리가 있다면 현재의 사다리에 +1 을 왼쪽 가로로 이어진 사다리가 있다면 현재의 사다리에 -1 연산을 한다고 할 수있다.
  그러므로 ladders 를 최신화 할때는 ladders[a][b] = 1, ladders[a][b + 1] = -1 을 대입한다. 예를 들어 1,1 에 사다리를 놓는다 하면 이 사디로 인해 1번에 있던 사람은 가로 1번선에서 +1을 해 2번으로, 2번 있던 사람은 -1을 해 1번으로 이동 할 것이다.
• ghost_leg_check() 함수의 내부에 대해 알아보자. cur를 현재 탐색중인 사다리라고 하자, cur의 정보를 ladders[i][cur]에 맞게 최신화하며 i번 사다리의 맨 끝인 j에 도착했다면 cur과 j 가 일치하는지 확인하고 아니라면 False를 반환하는 함수이다.

n, m, h = map(int, input().split())
ladders = [[0] * (n + 1) for _ in range(h + 1)]
lines = [list(map(int, input().split())) for _ in range(m)]
 # 입력으로 주어진 사다리를 b, b+1를 연결하며 1, -1로 최신화
for a, b in lines:
    ladders[a][b], ladders[a][b + 1] = 1, -1

candidates = []
for r in range(1, h + 1):
    for c in range(1, n):
        if ladders[r][c] == 0 and ladders[r][c + 1] == 0:
            candidates.append([r, c])


 # 주어진 사다리 조작의 조건에 맞는지 판단할 함수 선언
def ghost_leg_check():
    for j in range(1, n + 1):
        cur = j
        for i in range(1, h + 1):
            cur += ladders[i][cur]
        if cur != j:
            return False
    return True


 # 사다리를 놓을 수 있는 모든 경우를 탐색할 dfs 선언
def dfs(depth):
    global ans
    if ghost_leg_check():
        ans = min(ans, depth)
        return
    if depth >= 3:
        return
    for k in range(depth, len(candidates)):
        row, col = candidates[k]
        if ladders[row][col] == 0 and ladders[row][col + 1] == 0:
            ladders[row][col], ladders[row][col + 1] = 1, -1
            dfs(depth + 1)
            ladders[row][col], ladders[row][col + 1] = 0, 0


ans = 4
dfs(0)
print(ans if ans < 4 else -1)