👱‍♀️ ansohxxn

👱‍♀️ ansohxxn

개인적인 필기 노트

[고득점Kit][DP] 등굣길 ⭐⭐⭐

Date:     Updated:

카테고리:

태그:

C++로 풀이했습니다.
출처 : 프로그래머스 고득점 Kit 문제 풀이. https://programmers.co.kr/learn/challenges

[DP] 등굣길

난이도 ⭐⭐⭐

문제

image

image


내 풀이 ⭕

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(int m, int n, vector<vector<int>> puddles) {
	int answer = 0;

	// [n + 1][m + 1] 크기로 선언
	vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
	sort(puddles.begin(), puddles.end());

	// 갈 수 없는 테두리 영역은 -1 로 두르자. 미리 dp에 체크
	for (int i = 0; i < n + 1; i++)
	{
		if (i == 0)
		{
			for (int j = 0; j < m + 1; j++)
				dp[i][j] = -1;
		}
		else
			dp[i][0] = -1;
	}

	// 물 웅덩이 있는 곳은 -1 으로 미리 dp에 체크 
	for (int i = 0; i < puddles.size(); i++)
        dp[puddles[i][1]][puddles[i][0]] = -1;
		

	// dp 채워나가기 
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (dp[i][j] == -1)
				continue;

			// 1 행 1 열(집)까지의 경로 값은 1 로 한다. (0 으로 하면 아래 과정상 계속 0 으로만 업데이트 된다.)
			else if (i == 1 && j == 1)
				dp[i][j] = 1;

			// 현재 좌표 기준 왼쪽, 위쪽 모두에서 올 수 없는 경우 👉 바로 위,왼쪽 모두에 물 웅덩이가 있거나(-1), 바로 위, 왼쪽 좌표까지 올수 있는 경로가 모두 0 이거나(0) 
			else if (dp[i - 1][j] <= 0 && dp[i][j - 1] <= 0)
				dp[i][j] = 0;

			// 현재 좌표 기준 위쪽에서만 올 수 없는 경우 👉 1행이거나, 바로 위에 물 웅덩이가 있거나(-1), 바로 위 좌표까지 올수 있는 경로가 0 이거나(0) 
			else if (dp[i - 1][j] <= 0)
				dp[i][j] = dp[i][j - 1];

			// 현재 좌표 기준 왼쪽에서만 올 수 없는 경우 👉 1열이거나, 바로 왼쪽에 물 웅덩이가 있거나(-1), 바로 왼쪽 좌표까지 올수 있는 경로가 0 이거나(0) 
			else if (dp[i][j - 1] <= 0)
				dp[i][j] = dp[i - 1][j];

			// 현재 좌표 기준 왼쪽, 위쪽 이렇게 2가지 경우 모두에서 올 수 있는 경우 
			else
				dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % 1000000007;
		}
	}

	answer = dp[n][m];
	return answer;
}

점화식 👉 [i, j] 좌표까지 오는 경로의 수 = [i - 1, j] 좌표까지 오는 경로의수(위에서 아래로 오는) + [i, j - 1] 좌표까지 오는 경로의수(왼쪽에서 오른쪽으로 오는)

  • 이 문제에서 주의해야할 점은 n이 행이고 m이 열이라는 것이다. 또한 puddles[i][0]가 열이고 puddles[i][1]이 행이라는 것이다.
  • [n + 1][m + 1] 로 1 사이즈씩 더 크게 배열을 만들었다. 0 행 0 열을 벽으로 만들어 주기 위하여.. (0행 혹은 0 열로부터 온 좌표는 있을 수 없다.)
    • 1 행은 위(0 행)가 벽이기 때문에 아래 방향으로 올 순 없고 오른쪽 방향으로만 올 수 있다.
    • 1 열은 왼쪽(0 열)이 벽이기 때문에 오른쪽 방향으로 올 순 없고 아래쪽 방향으로만 올 수 있다.
    • 처음엔 그냥 왼쪽이 0 열일 때, 왼쪽이 0 행일 때 이렇게 if 문을 다르게 해주어서 처리 해 주었는데.. 사실 갈 수 없는게 벽 뿐만 아니라 물 웅덩이도 있고 값이 0 인 곳도 있으니 복잡해져서 그냥 1 사이즈 더 크게 배열을 만들고 0 행, 0 열을 모두 -1 로 둘러버렸다.

image

0 행, 0 열인 벽과 물 웅덩이는 갈 수 없는 곳이다. 이렇게 처음부터 갈 수 없도록 dp에 미리 저장한 곳은 -1로 저장했다.

	// 갈 수 없는 테두리 영역은 -1 로 두르자. 미리 dp에 체크
	for (int i = 0; i < n + 1; i++)
	{
		if (i == 0)
		{
			for (int j = 0; j < m + 1; j++)
				dp[i][j] = -1;
		}
		else
			dp[i][0] = -1;
	}

	// 물 웅덩이 있는 곳은 -1 으로 미리 dp에 체크 
	for (int i = 0; i < puddles.size(); i++)
        dp[puddles[i][1]][puddles[i][0]] = -1;

초기화 과정. ‘from’ 이 될 수 없는 곳인 0 행 혹은 0 열, 그리고 물 웅덩이를 미리 dp에 값을 저장해둔다.

	// dp 채워나가기 
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{

dp[i][j] 채워 나가기. (i와 j는 1 부터 n, m 까지.) if-else if 문의 순서가 굉장히 중요하다. if-else if 문 순서 배치에 신경써서 배열 범위를 벗어나 런타임 에러가 나지 않도록 한다. else if가 한번 참이였으면 아래의 else if문들은 조건도 아예 따지지 않고 넘어간다는 성질을 기억하자. ⭐⭐⭐⭐⭐

			if (dp[i][j] == -1)
				continue;

원래 부터 갈 수 없는 곳이라 -1로 초기화 되었던 곳이라면 (0 행 혹은 0 열, 그리고 물 웅덩이) dp[i][j]를 저장 할 필요가 없으므로 스킵. 이미 -1로 설정 되어 있으니까!


			// 1 행 1 열(집)까지의 경로 값은 1 로 한다. (0 으로 하면 아래 과정상 1 행 1 열이 계속 0 으로만 업데이트 된다.)
			else if (i == 1 && j == 1)
				dp[i][j] = 1;

출발지인 집은 1로 설정했다. 1 행같이 위는 0 행인 벽이라 위에서 올 순 없고 왼쪽에서만 올 수 있는 그런 곳은, 왼쪽 좌표에 오기까지의 경로의 수를 그대로 물려받을 것이기 때문에 0 이면 안된다. 아래 아래 점화식 참고.

			// 현재 좌표 기준 왼쪽, 위쪽 모두에서 올 수 없는 경우 👉 바로 위,왼쪽 모두에 물 웅덩이가 있거나(-1), 바로 위, 왼쪽 좌표까지 올수 있는 경로가 모두 0 이거나(0) 
			else if (dp[i - 1][j] <= 0 && dp[i][j - 1] <= 0)
				dp[i][j] = 0;

image

왼쪽과 위쪽 모두 물 웅덩이거나 벽이거나 경로의 수 값이 0 인 좌표여서 왼쪽, 위쪽 모두에서 올 수 없다면 해당 dp[i][j] 좌표까지 올 수 있는 경로는 전혀 없으므로 0 으로 저장한다. 그림처럼 빨간 글씨 좌표들 같은 경우는 그 좌표로 이동할 수 있는 경로가 없다. 오른쪽 아래쪽으로 이동하여 도착할 수 있는 경로들이 막혀있어서.

			// 현재 좌표 기준 위쪽에서만 올 수 없는 경우 👉 1행이거나, 바로 위에 물 웅덩이가 있거나(-1), 바로 위 좌표까지 올수 있는 경로가 0 이거나(0) 
			else if (dp[i - 1][j] <= 0)
				dp[i][j] = dp[i][j - 1];

왼쪽에서는 올 수 있는데 위쪽에서만 올 수 없는 경우, 점화식 👉 [i, j] 좌표 까지의 경로의 수 = [i - 1][j] 좌표까지의 경로의 수 (위쪽 좌표를 그대로 물려 받음)

왼쪽에서 올 순 없으므로 위쪽 좌표의 경로의 수를 그대로 물려 받아 저장된다. 왼쪽에서도 올 수 없었다면 진작 위의 else if 를 만나 이 else if 엔 걸리지 않는다.

			// 현재 좌표 기준 왼쪽에서만 올 수 없는 경우 👉 1열이거나, 바로 왼쪽에 물 웅덩이가 있거나(-1), 바로 왼쪽 좌표까지 올수 있는 경로가 0 이거나(0) 
			else if (dp[i][j - 1] <= 0)
				dp[i][j] = dp[i - 1][j];

위쪽에서는 올 수 있는데 왼쪽에서만 올 수 없는 경우, 점화식 👉 [i, j] 좌표 까지의 경로의 수 = [i ][j - 1] 좌표까지의 경로의 수 (왼쪽 좌표를 그대로 물려 받음)

위쪽에서 올 순 없으므로 왼쪽 좌표의 경로의 수를 그대로 물려 받아 저장된다.

			// 현재 좌표 기준 왼쪽, 위쪽 이렇게 2가지 경우 모두에서 올 수 있는 경우 
			else
				dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % 1000000007;

왼쪽 위쪽 모두에서 둘 다에서 올 수 있는 좌표의 점화식 👉 [i, j] 좌표까지 오는 경로의 수 = [i - 1, j] 좌표까지 오는 경로의수(위에서 아래로 오는) + [i, j - 1] 좌표까지 오는 경로의수(왼쪽에서 오른쪽으로 오는)

dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) !!! 문제에서 1000000007 를 나눈 나머지를 구해달라고 했는데, 테스트 케이스 중에 경로의 수가 20억 보다 커지는 경우도 있어서 그런 것 같다. 확실히는 잘 모르겠다.

	answer = dp[n][m];
	return answer;

최종적으로 학교 위치인 n행 m열에 대응하는 dp[n][m]에 집에서 학교까지 올 수 있는 모든 최단 경로의 개수가 저장되게 된다.


🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

댓글남기기

참고