| 시간 제한 | 메모리 제한 |
| 2초 | 512MB |
문제
(그림생략)
사다리 게임은 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을 출력한다.
풀이
N과 H의 범위에 따라 최대 300개의 자리에 가로선을 놓을 수 있다. 하지만 문제에서 가로선 3개로 해결되지 않는 경우는 탐색하지 않아도 된다고 정해놓았기 때문에 O((NH)3) 안에 완전 탐색이 가능하다. 시간제한은 2초로 넉넉하다. 하지만 단순한 탐색이 아니고, 구성된 사다리가 문제의 조건을 만족하는지 여부를 확인하는 것 또한 꽤 시간이 소요되므로 단순히 3차 시간 안에 해결될 것으로 기대할 수 없다. 엄밀히 따져보면 O((NH)4)인 셈인데 이렇게 되면 2초의 시간제한으로 해결할 수 없게 된다. 따라서 완전 탐색이 아닌 탈출 조건을 세워 백트래킹으로 해결해야 한다. 탈출 조건에 부합하는 경우에는 사다리의 조건 만족 여부를 확인하지 않는 식으로 시간을 아낄 수 있다.
1. 사다리 관리, 체크
사다리의 정보를 어떻게 관리할 것인지 정해보자. H+1행 N+1열의 배열 ladder을 만들어서 위에서부터 h번째 가로선으로 n번과 n+1번 세로선을 연결하는 경우, ladder[h][n] = 1로 저장한다. 예제 입력 3의 경우는 다음과 같이 표현된다.
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 1 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 |
N,M,H = map(int,input().split())
ladder = [[0]*(N+1) for _ in range(H+1)]
for _ in range(M):
a,b = map(int,input().split())
ladder[a][b] = 1주어진 사다리에서 i번째 세로선의 결과가 i번이 나오는지 확인하기 위해, O(NH) 선형탐색을 실시한다. 각각의 세로선에서 h를 1부터 H까지 탐색한다. ladder[h][i] == 1이라면 i 값이 1증가하고 ladder[h][i-1] == 1이라면 i 값이 1감소한다. 하나의 세로선을 탐색하고 i값이 변했다면 조건에 맞지 않는 사다리이고 모든 탐색을 마칠 때까지 달라진게 없다면 조건에 맞는 사다리이다.
def check(ladder,N,H):
for i in range(1,N+1):
k = i
for h in range(1,H+1):
if ladder[h][k]:
k += 1
elif ladder[h][k-1]:
k -= 1
if k != i:
return False
return True
2. 탐색
1번째 세로선의 위쪽부터 탐색을 시작해 다음 세로선으로 가로선을 이어줄 수 있는지 확인한다. 이때 가로선을 놓을 수 있는지 여부를 확인하며 가로선을 놓으면 재귀를 이용해 이후의 탐색 범위에 가로선을 놓아본다. 매 탐색마다 사다리를 확인해주어야 한다. 사다리를 놓는 것만 해도 경우의 수가 너무 많은데 사다리 확인까지 하게 되면 시간초과 확정이다. 탐색이 필요 없는 경우를 찾아 가지치기를 해줘야 한다.
문제에서 3개를 초과하는 가로선을 놓는 것이 최소인 경우는 -1을 출력하도록 제한했으므로 깊이우선탐색을 하되, 깊이 3을 넘어가면 탈출하도록 한다.
문제에서 출력해야 하는 것은 가로선의 위치가 아닌 최소 가로선의 수이므로 이전에 3이하의 깊이 d에서 해를 찾은 경우, d 이상의 깊이는 탐색할 필요가 없다. 그럼 위 조건과 합쳐서 초기 깊이 제한을 4로 두고, 탐색에서 해를 찾을 때마다 이 값을 줄여주는 방법으로 가지치기를 할 수 있다.
또 한 가지 걸어둘 수 있는 조건이 있는데 구현하지 않아도 시간초과는 아니라 포함시키지 않았다. i번째 세로선이 i번으로 연결되는 사다리는 세로선의 단면에 0 또는 짝수 개의 가로선이 연결되어 있어야 한다. 하나의 세로선을 탐색하고 다음 세로선으로 넘어갈 때 세로선에 각 면에 연결된 가로선의 수를 세어 홀수라면 탈출시켜 d가 아직 2 이상일 때의 탐색을 대폭 줄여줄 수 있을 것 같다.
정답 코드
import sys
input = sys.stdin.readline
N,M,H = map(int,input().split())
ladder= [[0]*(H+1) for _ in range(N+1)]
for _ in range(M):
a,b = map(int,input().split())
ladder[b][a] = 1
result = H*(N-1)-M+1
def Ladder(l):
for i in range(1,N+1):
t = i
for j in range(1,H+1):
if l[t][j] == 1:
t += 1
elif l[t-1][j] == 1:
t -= 1
if t != i:
return False
else:
return True
def DFS(l,k,c,h):
if k > 3:
return result
if Ladder(l):
return k
r = result
for j in range(h+1,H+1):
if l[c][j] == l[c-1][j] == l[c+1][j] == 0:
l[c][j] = 1
r = min(DFS(l,k+1,c,j),r)
l[c][j] = 0
for i in range(c+1,N):
for j in range(1,H+1):
if l[i][j] == l[i-1][j] == l[i+1][j] == 0:
l[i][j] = 1
r = min(DFS(l,k+1,i,j),r)
l[i][j] = 0
return r
result = DFS(ladder,0,1,0)
if result > (N-1)*H-M or result > 3 : result = -1
print(result)
