[프로그래머스] 경주로 건설 (DFS+DP) Python + 히든케이스 정리

https://school.programmers.co.kr/learn/courses/30/lessons/67259

프로그래머스

1. 문제보고 DFS/BFS를 떠올렸다

2. 처음에는 DFS이고 최단 경로로 탐색하려면 아래방향이나 오른쪽 방향을 먼저 탐색하는 greedy 방식인가? 라고 생각했다

3. 그리고 모든 경로를 탐색해야 하므로 백트래킹으로 풀었다. 

4. 테스트케이스에서 시간초과가 났다 

 

해결방법

- DFS 모든 경로 탐색에서 안되는 경로를 빨리 쳐내야 한다 !!

- DP 테이블을 이용한다. 

 

탐색하지 않을 경로의 재귀함수 탈출 방법

1. 현재 answer과 현재 경로까지 누적된 amount 값의 비교 : amount 가 더 큰 경우 재귀 탈출

2. DP 에 저장된 값으로 dp[x][y]와 amount 값을 비교한다. : amount 가 더 큰 경우 재귀 탈출 

 

또한 탐색 순서를 처음에는 하, 우, 상, 좌 로 했는데 이렇게 하면 edge case 가 걸렸고, 우, 하, 상, 좌 로 탐색한 경우 통과했다. 

INF = int(1e9)


def solution(board):
    answer = INF
    N = len(board)
    visited = [[False] * N for _ in range(N)]
    dp = [[INF] * N for _ in range(N)]
    # 상하 -> 상하 / 좌우 -> 좌우 100
    # 상하 -> 좌우 / 좌우 -> 상하 600
    #  아래 오른쪽 먼저 확인하기
    # 우, 하, 좌, 상 이 순서가 중요했음..
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]

    # 시간 초과 해결을 위해서 안되는 경로를 재귀함수 돌리기 쳐내야함
    def dfs(x, y, dir, amount):
        nonlocal answer

        if answer < amount:
            return
        # dp 값 갱신 or 현재 경로 버리기

        if dp[x][y] < amount:
            return
        else:
            dp[x][y] = amount

        if x == N - 1 and y == N - 1:
            answer = min(answer, amount)
            return

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < N and 0 <= ny < N and board[nx][ny] == 0 and not visited[nx][ny]:
                visited[nx][ny] = True
                if x == 0 and y == 0:  # 맨 처음 칸 확인
                    dfs(nx, ny, i, amount + 100)
                elif dir == i:  # 방향 같은 경우
                    dfs(nx, ny, i, amount + 100)
                else:
                    dfs(nx, ny, i, amount + 600)

                visited[nx][ny] = False
        # 맨 처음 시작

    dfs(0, 0, -1, 0)

    # answer = min(dp[N - 1][N - 1], answer)

    return answer

 

Hidden Case (TC 25)

 프로그래머스 질문하기를 뒤적거리면서 찾아낸 반례 testcase이다. 

[[0, 0, 0, 0, 0, 0, 0, 0], 
[1, 0, 1, 1, 1, 1, 1, 0], 
[1, 0, 0, 1, 0, 0, 0, 0], 
[1, 1, 0, 0, 0, 1, 1, 1], 
[1, 1, 1, 1, 0, 0, 0, 0], 
[1, 1, 1, 1, 1, 1, 1, 0], 
[1, 1, 1, 1, 1, 1, 1, 0], 
[1, 1, 1, 1, 1, 1, 1, 0]]

# answer = 4500

그림으로 표현하면 아래와 같이 생각되는데, 

위 경우 빨간 선의 값이 저장되게 하려면 우측부터 순회해서 DP값이 dp[3][4] = 2800으로 저장시키고, dp[4][4] = 2900으로 저장을 먼저 해두어야 한다. 

그렇지 않고 파란선부터 경로 탐색한 경우 빨간선 경로는 dp[3][4]에서 아래 코드에 의해서 버려지게 된다

if dp[x][y] < amount:
    return
else:
    dp[x][y] = amount

 

그런데 이 경우만 이런건지, 오른쪽 방향 먼저 순회하고 아래방향 순회하는것이 general 하게 맞는건지.. 헷갈려서 아직 좀 더 생각해봐야겠다 

 

 

반례 자료 출처:

https://school.programmers.co.kr/questions/42984

프로그래머스