[코테] 리트코드 파이썬 62번, 64번, 79번 2차원 리스트 최단거리 관련

62번 Unique Paths

Unique Paths - LeetCode

Unique Paths - LeetCode

2차원 리스트의 가로m, 세로n 길이가 주어졌을 때 왼쪽 위에서 오른쪽 아래로 이동할 수 있는 모든 경로의 수를 구하는 문제이다.

 

도착점에 도착하기 까지 출발점에서부터 세로로 m-1만큼 가로로 n-1만큼 이동해야 한다. 그렇기 때문에 m+n-2만큼의 움직임이 필요하다. 하나의 셀에서 오른쪽이나 아래쪽으로 움직일 수 있고 유일한 조합(Combination)의 경로를 찾아야 한다. 

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        return factorial(m+n-2) // factorial(m-1) // factorial(n-1)

---

64번 Minimum Path Sum

Minimum Path Sum - LeetCode

Minimum Path Sum - LeetCode

2차원 리스트에서 왼쪽 위에서 오른쪽 아래로 이동할 수 있는 모든 경로의 수 중 가장 비용이 적게 드는 경로를 찾아 그 비용을 리턴하는 문제이다.

 

이때까지 거리의 비용을 저장하는 배열을 matrix로 선언한다. 가로 첫줄과 세로 첫줄을, 해당 영역의 cost와 그 전 영역의 cost를 사용하여 초기화한다.

나머지 구역은, 해당 영역의 위와 왼쪽의 비용 중 더 작은 값을 선택하고 해당 영역의 cost를 더하여 초기화한다.

그 후 도착지인 오른쪽 아래의 cost를 리턴하면 가장 비용이 적게 드는 경로의 비용이 된다.

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        n = len(grid)
        m = len(grid[0])
        
        matrix = [[0]*m for i in range(n)]
        matrix[0][0]=grid[0][0]

        for i in range(1,m):
            matrix[0][i]=matrix[0][i-1]+grid[0][i]
        for i in range(1,n):
            matrix[i][0]=matrix[i-1][0]+grid[i][0]
        
        for i in range(1,n):
            for j in range(1,m):
                matrix[i][j]=min(matrix[i-1][j],matrix[i][j-1])+grid[i][j]
        return matrix[n-1][m-1]

---

79번 Word search

Word Search - LeetCode

Word Search - LeetCode

각 원소의 값이 알파벳으로 구성된 2차원 배열이 주어져 있다. 단어가 주어질 때, 2차원 배열의 경로로 특정 단어가 만들어질 수 있는 지 파악하는 문제이다.

 

2차원 리스트를 순회하면서 해당 좌표에서 시작되는 경로를 통해 주어진 문자열을 만들 수 있는 지 확인한다.

해당 좌표에서 동서남북을 확인하면서 각 알파벳과 같은 지 확인한다. 이때 pos라는 변수를 통해 몇 번째 알파벳까지 확인하였는지 확인하고 끝까지 탐색하였으면 true를 리턴한다.

더하여 특정구역의 문자가 중복되어 사용할 수 없기 때문에 재귀함수를 처리하는 동안 해당 범위를 알파벳이 아닌 None으로 바꿔둔다.

 

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        width = len(board[0])
        height = len(board)
        P = len(word)
        
        def search(r,c,pos):
            if pos >= P:
                return True
            elif 0 <= r < height and 0 <= c < width and board[r][c] == word[pos]:
                temp = board[r][c]
                board[r][c] = None
                if search(r+1,c,pos+1) or search(r-1,c,pos+1) or search(r,c+1,pos+1) or search(r,c-1,pos+1): 
                    return True
                board[r][c] = temp
                
        for r in range(len(board)):
            for c in range(len(board[0])):
                if search(r,c,0):
                    return True
        return False