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

---

1. 코드

def check():
    for i in range(n):
        start = i 
        for j in range(h):
            if i == 0:
                if graph[j][i] != 0:
                    i += 1
            elif i == n - 1:
                if graph[j][i - 1] != 0:
                    i -= 1
            else:
                if graph[j][i] != 0:
                    i += 1
                elif graph[j][i - 1] != 0:
                    i -= 1
        if start != i:
            return False
    return True
​
​
def dfs(idx, count):
    if count > 3:
        return
    if check():
        f[0] = True
        ans.append(count)
	
	# 2중 for문을 통해 접근하지 않고
	# divmod(idx, 열의 개수)로 [행][열]을 구했다.
    for i in range(idx, n * h):
        x, y = divmod(i, n)
        if graph[x][y] == 0 and y != n - 1:
            flag = False
            if y == 0:
                if graph[x][y + 1] == 0:
                    flag = True
            else:
                if graph[x][y - 1] == 0 and graph[x][y + 1] == 0:
                    flag = True
            if flag:
                graph[x][y] = 2
                dfs(i + 1, count + 1)  # 현재 idx보다 큰 부분을 탐색해야 한다.
                graph[x][y] = 0
​
​
ans = []
f = [False]
n, m, h = map(int, input().split())
graph = [[0] * n for _ in range(h)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a - 1][b - 1] = 1
​
dfs(0, 0)
if not f[0]:
    print(-1)
else:
    print(min(ans))

---

2. 후기

풀고나니 생각보다 코드는 단순했다. 마지막 열에는 사다리를 설치할 수 없다는 사실을 뒤늦게 깨달아서 시간초과에서 해맸다.