[LeetCode # 62 ~ 64] 문제 풀이

# 62. Unique Paths

M * N 크기의 Grid 가 주어졌을 때, Top-Left 부터 Bottom-Right 위치까지 이동하는 유일한 경로의 개수를 구하는 문제

* 이동은 Right, Bottom 방향으로만 가능하다.

 

오른쪽과 아래로만 이동이 가능하기 때문에 한 위치에서 오른쪽 위치 (몇 번을 이동하든) 로 가는 경로는 하나이고, 아래 방향도 마찬가지이다.

대각선 방향으로 이동하는 것은 오른쪽 -> 아래 / 아래 -> 오른쪽 의 경로만 존재하기 때문에 대각선 방향으로 이동하는 경우는 해당 위치의 바로 위칸까지 이동하는 경로 개수 + 왼쪽 위치로 이동하는 경로 개수로 구할 수 있다.

 

int uniquePaths(int m, int n) {
	int matrix[101][101] = { 0, };

	for (int j = 0; j < n; j++)
		matrix[0][j] = 1;

	for (int i = 1; i < m; i++) {
		matrix[i][0] = 1;
		for (int j = 1; j < n; j++) {
			matrix[i][j] = matrix[i - 1][j] + matrix[i][j - 1];
		}
	}
	return matrix[m - 1][n - 1];
}

 

# 63. Unique Paths II

위의 문제와 마찬가지로 M * N 크기의 Grid 가 주어지고 유일한 경로의 개수를 구하는 문제이다.

유일한 차이는 중간에 장애물이 있어 해당 칸으로는 이동이 불가능하다는 점이다.

 

# 62. 와 풀이는 동일하게 진행하지만, 장애물이 있는 경우는 해당 칸으로 이동하는 경로의 개수를 0으로 만든다.

 

int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
	int M = obstacleGrid.size(), N = obstacleGrid[0].size();
	if (obstacleGrid[0][0] == 1 || obstacleGrid[M - 1][N - 1] == 1)
		return 0;
	vector<vector<int>> ans(M, vector<int>(N, 0));
	for (int k = 0; k < N; k++) {
		if (obstacleGrid[0][k] != 1)
			ans[0][k] = 1;
		else
			break;
	}

	for (int i = 1; i < M; i++) {
		if (obstacleGrid[i][0] != 1)
			ans[i][0] = ans[i - 1][0];
		else
			ans[i][0] = 0;
		for (int j = 1; j < N; j++) {
			if (obstacleGrid[i][j] == 1)
				ans[i][j] = 0;
			else
				ans[i][j] = ans[i][j - 1] + ans[i - 1][j];
		}
	}
	return ans[M - 1][N - 1];
}

 

# 64. Minimum Path Sum

M * N Grid 가 주어지고 각각의 칸에는 임의의 값이 들어있을 때 Top-Left 칸에서 Bottom-Right 칸으로 이동할 때 가장 작은 합을 갖는 경로의 합을 찾는 문제

* 위와 마찬가지로 이동은 오른쪽 / 아래 방향으로만 가능하다.

 

우선 M * N 크기의 행렬을 만들고, 각 칸 별로 최소 합을 만드는 경로를 찾도록 했다.

경로는 위의 문제에서 구했듯 어떤 한 위치로 이동할 수 있는 경우는 해당 위치의 윗칸 / 왼쪽 칸에서 해당 칸으로 이동하는 방법밖에 존재하지 않는다.

따라서 어떤 위치까지 경로의 합의 최소값은 윗칸 / 왼쪽 칸까지의 합 중 작은 값 + 현재 칸의 값이 될 것이다.

 

int minPathSum(vector<vector<int>>& grid) {
    int N = grid.size(), M = grid[0].size();

    for (int i = 1; i<M; i++)
        grid[0][i] += grid[0][i-1];
    for (int i = 1; i<N; i++)
        grid[i][0] += grid[i-1][0];

    for (int i = 1; i<N; i++){
        for (int j = 1; j<M; j++){
            grid[i][j] += (grid[i-1][j] < grid[i][j-1] ? grid[i-1][j] : grid[i][j-1]);
        }
    }
    return grid[N-1][M-1];
}