leetcode hard : Unique Paths III

https://leetcode.com/problems/unique-paths-iii/description/

Unique Paths III - LeetCode

 

고놈 까다롭구만!

조건 고려해야될게 많아서 좀 까다롭긴했는데

그래도 풀만했다.

 

그냥 Backtracking 하면된다.

class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:

        emptyCount = 0
        startX, startY = -1, -1
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 0: emptyCount += 1
                if grid[i][j] == 1: startX, startY = i, j

        dx = [1, 0, -1 ,0]
        dy = [0, 1, 0, -1]
        def dfs(r, c, eCount):
            if r == -1 or r == len(grid) or c == -1 or c == len(grid[0]): return 0
            if grid[r][c] == -1: return 0
            if grid[r][c] == 1 and eCount != 0: return 0
            if grid[r][c] == 2:
                if eCount == emptyCount + 1 : return 1
                else: return 0

            save = grid[r][c]
            grid[r][c] = -1 
            s = 0
            for i in range(4):
                s += dfs(r + dx[i], c + dy[i], eCount + 1)
            grid[r][c] = save

            return s

        return dfs(startX, startY, 0)

 

empty칸의 개수를 먼저 세어놓는다.

dfs를 하면서 내가 현재 몇 개의 empty칸을 먹었는지 인자로 넘긴다.

도착지점에 왔을 때 내가 먹은 칸의 개수랑 먼저 세어놨던 empty칸의 개수가 맞으면 정답으로 세면 되는데 이때 eCount == emptyCount + 1을 한 이유는 도착지점에 오면서 eCount + 1을 넘겨받았기 때문에 도착지점도 empty한 칸으로 세어버렸기 때문이다.

 

그것외에 별다른 특이사항은 없다.