https://school.programmers.co.kr/learn/courses/30/lessons/42898
문제 해결 과정
착안
동적계획법(dynamic programming)을 활용해 문제를 해결하기 위해 시작점으로부터 $i$행 $j$열까지 도달하는 최단경로의 갯수를 저장할 배열 DP[$i$][$j$]을 사용하면, 오른쪽과 아래쪽으로만 이동 가능하므로 DP[$i$][$j$]에 도달하는 방법은
- DP[$i$][$j - 1$]이 웅덩이가 아니면 왼쪽 칸에서 오른쪽 방향으로 이동하여 도달하는 경우가 존재한다.
- DP[$i - 1$][$j$]이 웅덩이가 아니면 위쪽 칸에서 아래 방향으로 이동하여 도달하는 경우가 존재한다.
따라서 주어지는 웅덩이를 각각 배열에 표시하고, 위의 을 참고해 학교에 도달하는 최단경로의 개수를 계산한다.
구현
편의상, 웅덩이 좌표를 받아 지도에 미리 표시할 때 웅덩이 좌표에 해당하는 칸의 값은 음수(간단하게 -1로 사용)로 표시하여 문제를 해결하였다. 문제에서 주어지는 $m$, $n$의 값이 커질수록 학교에 도달할 수 있는 경우의 수가 크게 증가하므로 int 형 변수에서의 정수 오버플로(integer overflow)를 방지하기 위해 매 단계에서 1000000007로 값을 나눈 나머지를 저장해야 한다.
[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~
더보기
#include <vector>
#define denom 1000000007
using namespace std;
int DP[101][101];
int solution(int m, int n, vector<vector<int>> puddles)
{
DP[1][0] = 1;
for (vector<int> puddle : puddles)
DP[puddle[1]][puddle[0]] = -1;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (DP[i][j] == 0)
{
if (DP[i][j - 1] > 0)
DP[i][j] += DP[i][j - 1];
if (DP[i - 1][j] > 0)
DP[i][j] += DP[i - 1][j];
DP[i][j] %= denom;
}
return DP[n][m] % denom;
}
실행 결과
'C++ 코딩 문제 풀이 > 프로그래머스' 카테고리의 다른 글
[Programmers] 배달 (1) | 2023.12.21 |
---|---|
[Programmers] 피로도 (0) | 2023.12.21 |
[Programmers] 혼자 놀기의 달인 (0) | 2023.12.14 |
[Programmers] N-Queen (0) | 2023.12.12 |
[Programmers] 섬 연결하기 (0) | 2023.12.11 |
댓글