62. Unique Paths

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

Unique Paths - LeetCode

m*n 크기의 2차원 배열이 주어졌을 때, 시작점 [0, 0]부터 오른쪽 맨 아래 [m-1, n-1] 지점까지 오른쪽 혹은 아래로만 이동하면서 움직일 때 몇가지의 방법으로 도달할 수 있는지를 세는 문제이다.

모든 경우의 수를 세어야 하는 문제라는 점에서 전형적인 BFS 문제임을 알 수 있다.

 

[x, y]에서 갈 수 있는 수는 [x+1, y] 혹은 [x, y+1] 밖에 없으므로 path로 이 두가지의 방향을 설정해준다. 그리고 시작점 [0, 0]을 queue에 넣어두고, queue에서 path를 따라 두갈래길을 걸어가면서 해당 [x, y] 지점까지 몇가지의 방법으로 도달했는지 count 라는 2차원 배열에 기록해둔다. 

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        path = [[1,0], [0, 1]]
        
        count = [[0 for nn in range(n)] for mm in range(m)]
        count[0][0] = 1
        queue = [[0,0]]
        
        while queue:
            x, y = queue.pop(0)
            
            for p in path:
                if x + p[0] < m and y + p[1] < n:
                    if count[x + p[0]][y + p[1]] == 0:
                        queue.append([x+p[0], y+p[1]])
                    
                    count[x + p[0]][y + p[1]] += count[x][y]
                        
        return count[m-1][n-1]

여기서 주의해야 할 점은 하나의 위치에 대해서는 "한 번만" queue에 넣어주어야 한다는 것이다. 즉, queue에 다음 지점을 넣어줄 때 해당 지점에 대해 이미 계산을 했는지 하지 않았는지 확인을 해주어야 한다는 점이다. 해당 지점에 대해 한번 이상 계산을 한다면 중복값이 저장된다. 위의 코드에서는 계산을 했는지 하지 않았는지의 여부를 count[x][y]의 값이 0인지 (default 값인지) 아니면 그 이상인지로 확인해주고 있다.

 

복잡하다면 m=3, n=7의 예제로 한 단계씩 따라자보자. queue에서 꺼낸 [x, y] 지점의 오른쪽 칸과 아래쪽 칸에 대해서 몇가지의 방법으로 도달할 수 있는지 순서대로 출력하게 해보았다.

--- [0, 0] --- 
# [0, 0]의 오른쪽 칸과 아래쪽 칸으로는 1가지 unique path로 이동 가능하다
[1, 1, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0]
--- [1, 0] ---
[1, 1, 0, 0, 0, 0, 0]
[1, 1, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0, 0]
--- [0, 1] ---
# [1, 1]까지 도달할 수 있는 방법 = count[0][1] + count [1][0]
# 1) [0][0] -> [0][1] -> [1][1]
# 2) [0][0] -> [1][0] -> [1][1]
[1, 1, 1, 0, 0, 0, 0]
[1, 2, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0, 0]
--- [2, 0] ---
[1, 1, 1, 0, 0, 0, 0]
[1, 2, 0, 0, 0, 0, 0]
[1, 1, 0, 0, 0, 0, 0]
--- [1, 1] ---
[1, 1, 1, 0, 0, 0, 0]
[1, 2, 2, 0, 0, 0, 0]
[1, 3, 0, 0, 0, 0, 0]
--- [0, 2] ---
[1, 1, 1, 1, 0, 0, 0]
[1, 2, 3, 0, 0, 0, 0]
[1, 3, 0, 0, 0, 0, 0]
--- [2, 1] ---
[1, 1, 1, 1, 0, 0, 0]
[1, 2, 3, 0, 0, 0, 0]
[1, 3, 3, 0, 0, 0, 0]
--- [1, 2] ---
[1, 1, 1, 1, 0, 0, 0]
[1, 2, 3, 3, 0, 0, 0]
[1, 3, 6, 0, 0, 0, 0]
--- [0, 3] ---
[1, 1, 1, 1, 1, 0, 0]
[1, 2, 3, 4, 0, 0, 0]
[1, 3, 6, 0, 0, 0, 0]
--- [2, 2] ---
[1, 1, 1, 1, 1, 0, 0]
[1, 2, 3, 4, 0, 0, 0]
[1, 3, 6, 6, 0, 0, 0]
--- [1, 3] ---
[1, 1, 1, 1, 1, 0, 0]
[1, 2, 3, 4, 4, 0, 0]
[1, 3, 6, 10, 0, 0, 0]
--- [0, 4] ---
[1, 1, 1, 1, 1, 1, 0]
[1, 2, 3, 4, 5, 0, 0]
[1, 3, 6, 10, 0, 0, 0]
--- [2, 3] ---
[1, 1, 1, 1, 1, 1, 0]
[1, 2, 3, 4, 5, 0, 0]
[1, 3, 6, 10, 10, 0, 0]
--- [1, 4] ---
[1, 1, 1, 1, 1, 1, 0]
[1, 2, 3, 4, 5, 5, 0]
[1, 3, 6, 10, 15, 0, 0]
--- [0, 5] ---
[1, 1, 1, 1, 1, 1, 1]
[1, 2, 3, 4, 5, 6, 0]
[1, 3, 6, 10, 15, 0, 0]
--- [2, 4] ---
[1, 1, 1, 1, 1, 1, 1]
[1, 2, 3, 4, 5, 6, 0]
[1, 3, 6, 10, 15, 15, 0]
--- [1, 5] ---
[1, 1, 1, 1, 1, 1, 1]
[1, 2, 3, 4, 5, 6, 6]
[1, 3, 6, 10, 15, 21, 0]
--- [0, 6] ---
[1, 1, 1, 1, 1, 1, 1]
[1, 2, 3, 4, 5, 6, 7]
[1, 3, 6, 10, 15, 21, 0]
--- [2, 5] ---
[1, 1, 1, 1, 1, 1, 1]
[1, 2, 3, 4, 5, 6, 7]
[1, 3, 6, 10, 15, 21, 21]
--- [1, 6] ---
[1, 1, 1, 1, 1, 1, 1]
[1, 2, 3, 4, 5, 6, 7]
[1, 3, 6, 10, 15, 21, 28]

그런데 이렇게 확인하다보면, 맨 위쪽라인을 따라서 가거나 맨 왼쪽 라인을 따라서 내려가는 경우는 한가지 루트밖에 없다는 것을 알 수 있다. 그렇다면 이 값들을 먼저 채워준 후 나머지 값들은 2중 for문으로 count[x][y] = count[x-1][y] + count[x][y-1] 연산만 해주어도 된다는 것도 알 수 있다. 복잡한 queue 대신 for문을 사용해서 좀 더 단순하게 문제를 풀 수 있게 되었다.

 

이렇게 알게된 사실을 통해 정답 코드를 좀 더 간추려보았다.

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        count = [[1 for _ in range(n)] for _ in range(m)]
        
        for x in range(1, m):
            for y in range(1, n):
                count[x][y] = count[x-1][y] + count[x][y-1]

        return count[m-1][n-1]

경우의 수를 찾는 문제는 아래와 같은 조건식만 발견한다면 생각보다 쉽게 문제를 해결 할 수 있다.

특정 위치까지 갈 수 있는 방법 = 특정 위치의 윗칸까지 갈 수 있는 방법 + 특정 위치의 왼쪽 칸까지 갈 수 있는 방법
count[x][y] = count[x-1][y] + count[x][y-1]

처음부터 생각해내기는 어려울 수 있으니 나처럼 처음에는 brute force 형식으로 무모하지만 문제를 해결할 수 있는 방법을 고민해본 후에 조금씩 효율적으로 문제를 해결할 수 있는 방향으로 고쳐나가는 것도 좋을 것 같다.