하루 1문제 챌린지/Gold5

백준 17485 진우의 달여행(large) C++ 🚩

그린푸딩 2024. 1. 31. 23:32
728x90
반응형

https://www.acmicpc.net/problem/17485

 

17485번: 진우의 달 여행 (Large)

첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2 ≤ N, M ≤ 1000)이 주어진다. 다음 N줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소값은 100 이하의 자연수이다.

www.acmicpc.net

 

dfs로 탐색하면 어떨까 했는데 재귀로 1000*1000 =1000000정점을 탐색하는것을 시간/공간 복잡도 오류없이 해결할수 있을까 싶어서 dp로 풀었다. dfs,bfs 에 대한 시간/공간복잡도를 따로 정리해봐야겠다.. 

 

접근 방식 

1. 맨처음 행으로 진입, 맨끝행에서 달로 갈때도 방향을 계산해야 하나 했는데 첫행은 값 자체를, 끝 행에 도착하면 모든 계산이 끝난것으로 가정 

2. dp[i][j][dir]  = (i,j) 방향으로 이전 블록에서 dir 방향으로 옴, 만약 이전 블록에서 아래로 내려가는 방향 ↓ 이었다면 

dp[i][j][1]=min(dp[i-1][j][0],dp[i-1][j][2])+ arr[i][j] 가 된다.연속으로 같은 방향이되면 안되므로 (i-1,j) 으로는 이전에 ↓ 방향이 아닌 두 방향으로 와야 함 

3. 양 끝의 열의 경우에는 두 방향에서만 올 수 있음

4. 마지막 행에서 dp 행렬을 모두 구했을때 각 좌표로 모든 방향이 왔을때 값들인 dp[n-1][j][0],dp[n-1][j][1],dp[n-1][j][2] 양수일 경우에만 비교하여 최소값을 탐색

#include <iostream>
#include <vector>

using namespace std;

int main() {

	int n, m;

	cin >> n >> m;

	vector<vector<int>>arr;
	vector<vector<vector<int>>>dp;

	arr.assign(n, vector<int>(m, 0));
	dp.assign(n, vector<vector<int>>(m, vector<int>(3, 100000000)));

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
		}
	}
	

	for (int j = 0; j < m; j++) {
		for (int k = 0; k < 3; k++) {
			dp[0][j][k] = arr[0][j];
		}
	}

	for (int i = 1; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (j == 0) {//0,1
				dp[i][j][0] = min(dp[i - 1][j + 1][1], dp[i - 1][j + 1][2])+arr[i][j];
				dp[i][j][1] = min(dp[i - 1][j][0], dp[i - 1][j][2]) + arr[i][j];
			}
			else if (j == m - 1) {//1,2 
				dp[i][j][1] = min(dp[i-1][j][0],dp[i-1][j][2]) + arr[i][j];
				dp[i][j][2] = min(dp[i-1][j-1][0],dp[i-1][j-1][1]) + arr[i][j];

			}
			else {
				dp[i][j][0] = min(dp[i - 1][j + 1][1], dp[i - 1][j + 1][2]) + arr[i][j];
				dp[i][j][1] = min(dp[i - 1][j][0], dp[i - 1][j][2]) + arr[i][j];
				dp[i][j][2] = min(dp[i - 1][j - 1][0], dp[i - 1][j - 1][1]) + arr[i][j];
			}

		}
	}

	int mins = 100000000;
	for (int a = 0; a < n; a++) {
		for (int i = 0; i < m; i++) {
			for (int k = 0; k < 3; k++) {
				if (dp[n - 1][i][k])mins = min(mins, dp[n - 1][i][k]);
			}
		}
		
	}

	cout << mins;

}
728x90
반응형