정상까지 n개의 계단이 있는데 한 번에 한 칸 아니면 두 칸만 올라갈 수 있다. 얼마나 많은 unique 한 방법으로 정상까지 도달할 수 있느냐? 하는 문제이다. 저번 Unique Paths 문제와 비슷하게 출발점에서 도착점까지 가는 모든 방법의 수를 찾는 문제이므로 이 문제도 bfs로 접근할 수 있겠지만, 저번 문제를 풀 때와 같이 점화식을 찾으면 좀 더 쉽게 문제를 해결할 수 있다.
n번째 계단에 도달하기 위해서는 무조건 n-1번째 계단 아니면 n-2번째 계단을 밟아야만 한다. 이 두 계단을 통해서만이 n번째 계단에 도달할 수 있는 것이다. 이를 통해 아래와 같은 점화식을 유추해낼 수 있다.
n번째 계단에 가는 방법 = n-1번째 계단에 가는 방법 + n-2번째 계단에 가는 방법 path[n] = path[n-1] + path[n-2]
코드로 풀어서 써보자면 아래와 같다.
class Solution:
def climbStairs(self, n: int) -> int:
path = [1 for _ in range(n + 1)]
for i in range(2, n+1):
path[i] = path[i-1] + path[i-2]
return path[n]
path라는 리스트는 n+1 길이로 만들어주고 초기값을 1로 채워준다.
2번째 계단부터 새로 값을 계산해서 넣어줄 예정이라 초기값이 무엇인지 중요하지 않을 수도 있지만, 첫 번째 계단은 반드시 출발점에서 한 칸만 밟고 오는 한 가지 경우밖에 없고 또 path[2]부터 점화식을 사용하기 위해서라면 0번째 계단(출발점)에도 값 1을 넣어주는 것이 더 편하기 때문이다.
2번째 계단에 오르는 경우의 수는 문제 1번 예제와 같이 1칸+1칸 혹은 2칸 이렇게 두 가지 경우의 수밖에 없다.
즉, 2번째 계단에 가는 방법은 한 칸 전에서 올라오거나, 출발점에서 2칸을 바로 올라오거나 이 두가지 경우의 수밖에 없는 것이다.
이렇게 path[0] == path[1] == 1 값을 채워주고 path[2]부터는 점화식 알고리즘을 적용해 문제를 풀면 된다.
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] 지점의 오른쪽 칸과 아래쪽 칸에 대해서 몇가지의 방법으로 도달할 수 있는지 순서대로 출력하게 해보았다.
그런데 이렇게 확인하다보면, 맨 위쪽라인을 따라서 가거나 맨 왼쪽 라인을 따라서 내려가는 경우는 한가지 루트밖에 없다는 것을 알 수 있다. 그렇다면 이 값들을 먼저 채워준 후 나머지 값들은 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 형식으로 무모하지만 문제를 해결할 수 있는 방법을 고민해본 후에 조금씩 효율적으로 문제를 해결할 수 있는 방향으로 고쳐나가는 것도 좋을 것 같다.
