15684 - 사다리조작

시작은 3열에서 시작했으나, 종료는 4열에서 종료 = 실패

이 문제 풀이를 보니 bfs, dp로 푼사람들이 많던데... 아직 bfs로 생각하는 로직이 익숙하지 않다보니 무지성으로 dfs로 풀어버렸다. bfs, dp에 대한 익숙도를 높일 필요가 있어보인다.

 

어쨌든 처음에 TC를 통과하고 나서 제출하니 시간초과가 나왔다. 정말 시간초과가 제일 싫은게...논리적으로는 다 맞는데 여기서 효율성까지 따져야하니 어디서 고쳐야할지 아직은 감이 안 선다. ㅎㅎㅎ

 

일단 아래 코드는 통과한 코드이며, 시간초과를 해결한 방법 3가지를 정리해보았다.

• 시간초과 원인 1
  • dfs에서 모든 경우의 수를 탐색하다가 시간초과 나는 것을 방지하고자, 만약 문제에서 요구하는 "n번 시작 = n번 종료"인 경우에는 result를 True로 두고 더 이상 depth를 높여 탐색하지 않도록 하였다.
• 시간초과 원인 2
  • 하나라도 "n번 시작 = n번 종료"라면 굳이 더이상 찾아볼 필요도 없이 False이므로 이부분에 대해서도 처리해주었다.
• 시간초과 원인 3
  • 내가 짠 로직에 의하면 graph에 다리가 놓은 n, n+1번째 열에 1로 구분을 둔다. 그런데 만약 2번, 3번 열이 연결되어있고, 4번, 5번 열이 연결되어 있다고 가정하면 [0, 0, 1, 1, 1, 1]이 된다. 그럼 3번,4번이 연결되어있다고 오해할 소지가 있다. 이를 구분하고자 connectBridge에 [행, 열, 열+1] 이라는 연결정보를 둔 리스트를 쌓아뒀다. 그런데 이부분 때문에 9% 지점에서 시간초과가 나는 것이다. 그래서 이를 2차원 배열 형태로 두고, 현재 지점으로 부터 1인 경우에는 무조건 '오른쪽' 사다리와 연결되어있다는 가정하에 사다리간의 연결여부를 표시하였다. 그러니 해당 시간초과 문제는 무사히 해결되었다.

 

from copy import deepcopy
def moveDestination(graph, connectBridge):
    resultList = [False]*N
    for row in range(1, N+1):
        firstRow = row
        col = 1
        down = False
        while col <= H:
            if graph[col][row] == 0:
                col+=1
            elif (graph[col][row] == 1) and (down == True):
                col+=1
                down = False
            elif connectBridge[col][row] == 1:
                row+=1
                down = True
            else:
                row-=1
                down = True

        if row == firstRow:
            resultList[row-1] = True
        # 시간초과 원인2
        else:
            return False
    return True

def addBridge(bridge, copyGraph, copyConnectBridge):
    global result
    
    # 시간초과 원인1
    if result == True:
        return
    
    if bridge == plus:
        if moveDestination(copyGraph, copyConnectBridge):
            result = True
        return

    for i in range(1, H+1):
        for j in range(1, N):
            if copyGraph[i][j] == 0 and copyGraph[i][j+1] == 0 :
                copyGraph[i][j] = 1; copyGraph[i][j+1] = 1
                copyConnectBridge[i][j] = 1
                addBridge(bridge+1, copyGraph, copyConnectBridge)
                copyGraph[i][j] = 0; copyGraph[i][j + 1] = 0
                copyConnectBridge[i][j] = 0

N, M, H = map(int, input().split())
graph = [[0]*(N+1) for _ in range(H+1)]
# 시간초과 원인3
connectBridge = [[0]*(N+1) for _ in range(H+1)]
bridgeCnt = M
for i in range(M):
    a, b = map(int, input().split())
    # 다리가 있어서 오른쪽으로 이동 가능
    graph[a][b] = 1
    graph[a][b+1] = 1
    connectBridge[a][b] = 1
for plus in range(5):
    if plus == 4:
        print(-1)
        break

    result = False
    addBridge(0, deepcopy(graph), deepcopy(connectBridge))
    if result == True:
        print(plus)
        break