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

solution

import sys
input = sys.stdin.readline

N,M,H = map(int,input().split())
board = [[0] * N for _ in range(H) ]
for i in range(M):
    a,b = map(int,input().split())
    board[a-1][b-1] = 1
ans = 100

def is_answer():
    global board

    for start in range(N):
        index = start

        for horizon in range(H):
            try :
                if board[horizon][index] == 1:
                    index += 1
                    continue
                
                if board[horizon][index-1] == 1:
                    index -= 1
                    continue
            except :
                continue
        end = index  
        if start != end:
            return False
    return True
    

def dfs(index, x):
    global board
    global ans

    if is_answer():
        ans = min(ans,index)
        return

    if index == 3:
        return

    for a in range(x, H):
        for b in range(N-1):
            if board[a][b] == 1:
                continue
            
            try:
                if board[a][b-1] == 1:
                    continue
                if board[a][b+1] == 1:
                    continue
            except :
                continue

            board[a][b] = 1
            dfs(index+1,a)
            board[a][b] = 0

dfs(0,0)
if ans == 100: print(-1)
else: print(ans)

아이디어

문제를 읽고 나서 사다리를 전부 한 번씩 생각이 들었다. 가로선을 놓을 수 있는 곳을 배열로 만들고 dfs를 통해 탐색을 했다.
완탐으로 모든 경우의 수를 탐색했을 때 시간초과가 나는 것을 확인했다.
백트래킹을 통해서 경우의 수를 줄여줘야할텐데 어떤 경우의 수를 줄여줘야할지 감이 오지 않았다.

포인트

다른 사람이 작성한 코드를 살펴보고 처음 짰던 내 코드와 비교를 해봤다.

1. 나는 왜 재귀를 4번 돌았을까?

DFS로 완탐을 구현할 때 탈출 조건을 검사하는 부분과 정답을 검사하는 부분의 순서가 중요했다.

# 내 코드
def dfs(index):
	if index == 4:
    	return
        
    if is_answer():
    	ans = min(ans.index)
        return

# 고친 코드
def dfs(index):
	if is_answer():
		ans = min(ans, index)
		return

	if index == 3:
		return

원래 코드는 재귀를 모든 탐색에서 한번씩 더 호출하기 때문에 시간 복잡도가 배로 늘어나버리는 불상사가 발생한다. DFS는 탈출조건 -> 정답검사 -> 재귀호출 이렇게 생각하고 있었기 때문에 재귀를 한 번 더 호출하는 코드를 짜게 된 것 같다. 정답 검사를 탈출 조건보다 우선 수행하여 재귀를 호출하는 횟수를 줄였다.

2. 백트래킹은 필수!

완전탐색으로 구현을 하고, 재귀 호출을 줄여봐도 결국 시간초과의 늪에 빠졌다. 이 문제에서 시간초과가 나지 않는 중요한 포인트는 "사다리를 놓고 나서 이전에 검사했던 자리에는 사다리를 놓을 필요가 없다." 이다. 코드를 한번 보자.
내가 짠 코드에서는 재귀호출을 통해서 사다리를 놓는다.

# 내 코드
def dfs(index):
	# ...탈출조건 ...정답조건
	
    #재귀호출 시
    for a in range(H): # 사다리의 가로 수만큼
    	for b in range(N-1): # 세로 수 - 1 만큼
			if can_place_ladder(board[a][b]):
            	board[a][b] = 1
                dfs(index+1)
                board[a][b] = 0

# 고친 코드
def dfs(index, x):
	# ...탈출조건 ...정답조건
	
    #재귀호출 시
    for a in range(x,H): # 이전에 놓았던 사다리 index부터 검사 시작
    	for b in range(N-1): # 세로 수 - 1 만큼
			if can_place_ladder(board[a][b]):
            	board[a][b] = 1
                dfs(index+1,a)
                board[a][b] = 0

두 코드를 비교해보면 이전에 놓았던 사다리 자리를 dfs의 인자로 전달해주고 그 자리부터 탐색을 시작하는 것을 시작한다. 기존의 코드는 사다리를 놓고 재귀로 다음 사다리를 놓으려고 할 때 처음부터 탐색을 시작한다. 고친 코드는 사다리를 놓은 뒤, 그 사다리의 x 위치를 인자로 전달하여 그 위치부터 탐색을 시작한다. 원래 x와 y를 둘 다 전달하면 더 시간이 적게 걸리는 코드가 되겠지만 x만 해도 충분할 것이라고 생각했다.

아 x는 가로선이다.

느낀점

• 알고리즘에 어느정도 자신감이 붙어서인지 실수가 잦아졌다.
  print()를 지우지 않고 제출하여 출력초과가 나고, 문제를 꼼꼼히 읽지 않아서 사다리의 최소 갯수를 구해야하는데 그냥 사다리의 갯수만 구했다.
  문제 뿐만 아니라 내가 짠 코드도 꼼꼼히 읽지 않는다. vscode를 사용하다가 자동으로 import된 라이브러리 때문에 런타임에러가 3번이나 났다.
  이상한 라이브러리 import를 하면 내용을 보여주지 않는 런타임에러가 나는 걸 처음 알았다.

• 파이썬은 세상에서 제일 느리다. C++로 풀어도 시간초과가 날까? C++로 한 번 풀어봐야겠다.