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


class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        r, c = len(grid), len(grid[0])
        queue = deque([])
        ans = []
        start, end, cnt = None, None, 0
        for i in range(r):
            for j in range(c):
                if grid[i][j] == 1 : start = (i, j)
                if grid[i][j] == 2 : end = (i, j)
                if grid[i][j] != -1 : cnt += 1
        queue.append([start])
        while queue :
            cur = queue.popleft()
            i, j = cur[-1]
            if (i, j) == end and len(cur) == cnt :
                ans.append(cur)
                continue
            if i != 0 and grid[i-1][j] != -1 and (i-1, j) not in cur :
                queue.append(cur + [(i-1, j)])
            if i != r-1 and grid[i+1][j] != -1 and (i+1, j) not in cur :
                queue.append(cur + [(i+1, j)])
            if j != 0 and grid[i][j-1] != -1 and (i, j-1) not in cur :
                queue.append(cur + [(i, j-1)])
            if j != c-1 and grid[i][j+1] != -1 and (i, j+1) not in cur :
                queue.append(cur + [(i, j+1)])
        return len(ans)


난이도가 hard고, 일반적인 기법으로는 시간초과가 날 것 같은 문제라서 보자마자 엄청 긴장했으나..

m * n <= 20 조건으로 인해 엄청 쉬운 문제가 된다.

경로를 저장하기 때문에 visit check는 각각의 경로 안에서 직접 하면 된다..