63-moran991231.md

63. Unique Paths II

Solution 1

• 시간복잡도 : O(MN)

• 알고리즘 : Full Search+Dynamic Programming

• 풀이 설명 :

  고등학생 때 배운 길찾기 문제와 동일하다. 장애물이 있는 길은 지나갈 수 없을 때, 최단경로의 가짓수를 구하는 문제이다.

  가로 m칸, 세로 n칸으로 이루어진 길이 입력 obstacleGrid(줄여서 og)에 주어진다. 지나갈 수 있는 칸은 0, 장애물이 있어서 지나갈 수 없는 칸은 1로 주어진다. 장애물은 여러개가 있을 수 있다.

  • og[0][0]에서 출발하여 og[n-1][m-1]에 도착한다. 출발지나 도착지에 장애물이 있다면 출력은 0이다.

  • 완전탐색을 통해 장애물이 있는 칸을 1이 아닌 -1로 바꾸어 주었다.

  • 점화식 og[i][j] = og[i-1][j] + og[i][j-1]을 이용하려고 한다.

    • 경계조건이자 초기조건인 i=0혹은 j=0인 og[i][j]의 값을 설정해 주어야 한다. og[0][0]부터 og[i][0]까지는 직선경로인데, 길목에 장애물이 없으면 og[i][0]=1, 장애물이 있으면 og[i][0]=0이다. 비슷한 방법으로 og[0][j]도 설정해 준다.
    • 내가 사용한 방법은og[0][0]=1, og[i][0] = og[i][0] + og[i-1][0]이다. 이전에 완전탐색을 통해 장애물이 있는 칸의 값을 -1로 바꿔주었으므로, og[i][0]에 장애물이 없다면 1 저장되고, 장애물이 있다면 og[i][0], og[i+1][0], ...의 값들은 0으로 저장될 것이다. 아래 코드에는 og[i][0] = Math.max(og[i][0] + og[i - 1][0], 0)로, max연산이 사용되었는데, 장애물(-1)을 여러번 만나도 og[i][0]의 값을 음수가 아닌 0으로 유지하기 위함이다.

  • 점화식 적용

    • i=0이거나 j=0인 항은 이미 1또는 0의 값으로 초기화했다. 1<= i < r, 1<= j < c의 값에 점화식을 사용하면 된다. (r, c는 각각 og의 행과 열의 개수이다.)
    • og[i][j]의 값을 검사하여 장애물(-1)이 있으면 해당 칸은 지나갈 수 없으므로 0을 저장하고, 그것이 아니면 점화식의 식을 적용한다.

  • 도착지 og[r-1][c-1]의 값이 구하고자하는 최단경로의 가짓수이다.

​

• 소스코드 :

class Solution {
	public int uniquePathsWithObstacles(int[][] obstacleGrid) {
		int[][] og = obstacleGrid;
		int r = obstacleGrid.length, c = obstacleGrid[0].length;

		if (og[0][0] == 1) // 출발 칸에 장애물이 존재하는 경우
			return 0;

		for (int i = 0; i < r; i++)
			for (int j = 0; j < c; j++) {
				if (og[i][j] == 1) {
					og[i][j] = -1;
				}
			}

		og[0][0] = 1;
		for (int i = 1; i < r; i++)
			og[i][0] = Math.max(og[i][0] + og[i - 1][0], 0);

		for (int j = 1; j < c; j++)
			og[0][j] = Math.max(og[0][j] + og[0][j - 1], 0);

		for (int i = 1; i < r; i++) {
			for (int j = 1; j < c; j++) {
				if (og[i][j] != -1)
					og[i][j] = og[i - 1][j] + og[i][j - 1];
				else
					og[i][j] = 0;
			}
		}

		return og[r - 1][c - 1];
	}
}