[LeetCode] Hard - 980 Unique Paths III

▶980 - Unique Paths III

▶문제

You are given an m x n integer array grid where grid[i][j] could be:

• 1 representing the starting square. There is exactly one starting square.
• 2 representing the ending square. There is exactly one ending square.
• 0 representing empty squares we can walk over.
• -1 representing obstacles that we cannot walk over.

Return the number of 4-directional walks from the starting square to the ending square, that walk over every non-obstacle square exactly once.

 

▶예제

Example 1:

Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output: 2
Explanation: We have the following two paths: 
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)

Example 2:

Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,0,2]]
Output: 4
Explanation: We have the following four paths: 
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
2. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
3. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
4. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)

Example 3:

Input: grid = [[0,1],[2,0]]
Output: 0
Explanation: There is no path that walks over every empty square exactly once.
Note that the starting and ending square can be anywhere in the grid.

 

▶풀이

dfs를 이용해서 문제를 풀었는데, hard문제 치고는 쉬운 편이었다.

시작 i, j와 끝나는 i, j 그리고 갈 수 있는 길의 수를 파악해서 저장해 둔다.

이를 이용해서 dfs를 돌면서 갈 수 있나 확인해 보고, 끝에 도달했는데 cnt가 0이라면 answer을 증가시켜 준다.

 

dfs 중간에 grid[r][c] = -1로 해주는 이유는, dfs를 돌면서 이미 왔던 경로를 가지 않기 위해서이다.

dfs가 끝나고 돌아오게 되면 다시 0으로 바꿔준다.

class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        def dfs(r, c, cnt):
            cnt -= 1
            if r == fr and c == fc:
                if cnt == 0:
                    self.answer += 1
                return
            grid[r][c] = -1
            for i in range(4):
                dr = r + dx[i]
                dc = c + dy[i]
                if 0 <= dr < len(grid) and 0 <= dc < len(grid[0]) and grid[dr][dc] != -1:
                    dfs(dr, dc, cnt)
            grid[r][c] = 0


        cnt = 0
        self.answer = 0
        sr, sc, fr, fc = -1, -1, -1, -1
        dx = [-1, 1, 0, 0]
        dy = [0, 0, -1, 1]
        for i in range(len(grid)):
            for j in range(len(grid[i])):
                if grid[i][j] != -1:
                    cnt += 1
                if grid[i][j] == 1:
                    sr, sc = i, j
                elif grid[i][j] == 2:
                    fr, fc = i, j
        
        dfs(sr, sc, cnt)

        return self.answer

 

leetcode를 11월 말에 시작을 해서 12월에는 매일 문제를 풀었다.

한 달을 매일 문제를 푼다면 이런 뱃지를 주는 것 같다.

나름 뿌듯하고 의미 있는 것 같다.

내년에는 일이 있는 게 아니라면, 매월 뱃지를 받아봐야겠다.