문제 링크
https://www.acmicpc.net/problem/15684
🕒 Python 풀이시간: 60분
n,m,h=map(int,input().split())
board=[[0]*(n+2) for _ in range(h+2)]
for _ in range(m):
a,b=map(int,input().split())
board[a][b]=1
def play_ladder_game():
for i in range(1,n+1):
x,y=0,i
while True:
if x==h+1:
if y!=i:
return False
break
if board[x][y-1]==1:
y-=1
elif board[x][y]==1:
y+=1
x+=1
return True
def dfs(cnt,start_h,start_n):
global answer
if cnt>3 or cnt>=answer:
return
if cnt<=3:
tf=False
# for i in range(h+1):
# print(board[i])
# print()
tf=play_ladder_game()
if tf:
answer=min(answer,cnt)
return
for i in range(start_h,h+1):
if start_h!=i:
start_n=1
for j in range(start_n,n):
if board[i][j]==1:
continue
if board[i][j-1]==1:
continue
if board[i][j+1]==1:
continue
cnt+=1
if cnt>=answer:
cnt-=1
return
board[i][j]=1
dfs(cnt,i,j+1)
board[i][j]=0
cnt-=1
answer=1e9
dfs(0,1,1)
if answer!=1e9:
print(answer)
else:
print(-1)🪜 사다리 게임 최적화 방법
세로가 H줄, 가로가 N줄인 사다리를 그릴 수 있는 상황에서 이미 세로줄은 사다리가 있고 M개의 사다리를 가로를 놓을 수 있는 N줄에 이미 놓았을 때, 최소의 사다리를 가로로 추가해서 시작점과 끝점의 가로 번호가 같게 만드는 문제이다. 이 때 3개 이내로 만들지 못하면 -1을 출력한다.
DFS를 통한 백트래킹으로 사다리를 놓아가면서 문제를 풀 수 있다고 생각하였다. DFS로 cnt를 통해 사다리를 놓고 3개 이하일 때까지는 사다리 게임을 진행해보아서 정답을 구할 수 있도록 시작지점과 끝지점의 가로 좌표가 일치하는지 확인한다. 최소값이 갱신되면 이미 갱신된 값보다 cnt의 값이 커지거나 같을 때는 검사할 필요가 없으므로 return 시켰다.
여기서 시간초과가 발생하였다. 2차원 배열을 통하여 백트래킹을 진행할 때, 순열로만 놓는 방법을 사용해보아서 조합이 가능하다는 사고에 도달하지 못하였다. 조합을 위해 세로 좌표는 그대로 가져가도 되지만 들어오는 값이 바뀌면 가로 값을 0으로 리셋해서 새로운 층에서는 새롭게 탐색할 수 있도록 하였고 가로 축의 경우에는 +1을 해주어서 전에 탐색한 부분은 탐색하지 않도록 하였다.
즉, 조합을 놓는 식으로 사다리를 배치하니 시간초과를 해결하였고 좌표값을 이동시키면서 사다리를 놓는 최솟값을 구하면 된다. 앞으로는 백트래킹을 무조건 순열로 생각할게 아니라 백트래킹의 목적인 경우의 수를 구할 때, 중복이 가능한지, 순서가 중요한지 등의 순열, 조합, 중복의 조건들을 확인하고 문제에 접근하여야 겠다.
이렇게 Python로 백준의 "사다리 조작" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊
