320x100
문제 : https://leetcode.com/problems/unique-paths-iii/
m x n 정수형 배열 grid가 주어진다.
1 : 시작 지점. (1개 존재)
2 : 종료 지점. (1개 존재)
0 : 걸을 수 있는 곳
-1 : 장애물
상하좌우 4방향으로 이동가능할 때, 시작지점에서 종료지점으로 갈 수 있는 방법의 수를 구하라.
백트래킹.
시작지점부터 장애물이 아닌 곳으로 이동하면서 이동횟수를 저장하면서 상하좌우 방향으로 탐색한다.
탐색하면서 지나간 자리는 다시 못 지나가게 별도의 플래그 배열에 탐색한 위치는 표시를 해둔다.
종료지점에 도달했을 때, 걸음의 수가 grid 배열의 0, 2 cell의 수와 같다면 정답이 가능하므로 정답 방법의 수에 1을 더한다.
시간복잡도는..?
소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/hard/980.%20Unique%20Paths%20III.cpp
320x100
'알고리즘 문제 > Leetcode' 카테고리의 다른 글
[Leetcode] 67. Add Binary (0) | 2021.11.04 |
---|---|
[Leetcode]11. Container With Most Water (0) | 2021.11.03 |
[Leetcode] 130. Surrounded Regions (0) | 2021.11.01 |
[Leetcode] 222. Count Complete Tree Nodes (0) | 2021.10.29 |
[Leetcode] 437. Path Sum III (0) | 2021.10.18 |
댓글