[백준] 17485번 진우의 달 여행 (Large) (C++)

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

 

 

이 문제는 N X M 격자 그래프가 주어지며 진우는 왼쪽 대각선 아래 방향, 아래 방향, 오른쪽 대각선 아래 방향으로 움직일 수 있다.

 

이때 최소한으로 가장 아래까지 도착하는 연료의 최소값을 출력해야 한다.

 

이때 이전방향으로 오는 방향을 다시 사용할 수 없다.

 

따라서 제약조건을 잘만 처리하면 최소값을 dp를 사용해서 구할 수 있다고 생각하였다. dfs로는 배열의 크기가 너무 커서 안될것 같아서 바로 배제하였다.

 

처음 풀었을때는 3가지 방향에 대해 이전 좌표를 가져오고 이제 3방향을 움직여야 하는것에 대해 조건 처리를 해주었는데 

 

다른 스터디 선배의 풀이를 보고 저렇게도 풀 수 있구나 생각하였다.

 

내 풀이

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

struct horse {
    int x;
    int y;
    int dir;
};

// int dx[] = {-1, 1, 0, 0, 1, -1, -1, 1};
// int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
// int dx[] = {0, 0, 1, -1};
// int dy[] = {1, -1, 0, 0};
int dx[] = {1, 1, 1};
int dy[] = {-1, 0, 1};
int N, M;
int graph[1001][1001];
int dp[1001][1001][3];

void Init() {
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            for(int k = 0; k < 3; k++) {
                dp[i][j][k] = MAX;
            }
        }
    }
}

void solve() {
    for(int j = 0; j < M; j++) {
        for(int k = 0; k < 3; k++) {
            dp[0][j][k] = graph[0][j];
        }
    }

    for(int i = 1; i < N; i++) {
        for(int j = 0; j < M; j++) {
            for(int k = 0; k < 3; k++) {
                int prevx = i-1;		// 이전 3방향에 대한 좌표 가져옴
                int prevy = j - dy[k];

                if(prevy < 0 || prevy >= M) continue;		// 범위 초과

                int cost = MAX;

                for(int d = 0; d < 3; d++) {		// 이동해야하는 3방향 탐색
                    if(k == d) continue;			// 같은 방향이면 제외
                    cost = min(cost, dp[prevx][prevy][d]);
                }
                if(cost != MAX) dp[i][j][k] = cost + graph[i][j];
            }
        }
    }

    int answer = MAX;

    for(int j = 0; j < M; j++) {
        for(int k = 0; k < 3; k++) {
            answer = min(answer, dp[N-1][j][k]);
        }
    }

    cout << answer;
}

void input() {
    cin >> N >> M;

    Init();

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            cin >> graph[i][j];
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}

 

이렇게 이전 3방향의 좌표를 가져오고 현재 3방향에 대해 같은 방향은 제외한 풀이를 하였는데

 

점화식을 사용한 풀이가 있어서 참고하였다.

 

 

다른풀이

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

struct halloween {
    int cnt;
    int score;
};

// int dx[] = {-1, 1, 0, 0, 1, -1, -1, 1};
// int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int N, M;
int graph[1002][1002];
int dp[1004][1004][3];

void solve() {
    for(int j = 1; j <= M; j++) {
        dp[0][j][0] = dp[0][j][1] = dp[0][j][2] = graph[0][j];
    }

    for(int i = 1; i < N; i++) {
        for(int j = 1; j <= M; j++) {
            dp[i][j][0] = min(dp[i-1][j-1][1], dp[i-1][j-1][2]) + graph[i][j];
            dp[i][j][1] = min(dp[i-1][j][0], dp[i-1][j][2]) + graph[i][j];
            dp[i][j][2] = min(dp[i-1][j+1][1], dp[i-1][j+1][0]) + graph[i][j];
        }
    }

    int answer = MAX;

    for(int j = 1; j <= M; j++) {
        for(int k = 0; k < 3; k++) {
            answer = min(answer, dp[N-1][j][k]);
        }
    }

    cout << answer;
}

void Init() {
    for(int i = 0; i < N; i++) {
        for(int j = 0; j <= M+2; j++) {
            for(int k = 0; k < 3; k++) {
                dp[i][j][k] = MAX;
            }
        }
    }
}

void input() {
    cin >> N >> M;

    for(int i = 0; i < N; i++) {
        for(int j = 1; j <= M; j++) {
            cin >> graph[i][j];
        }
    }

    Init();
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}

 

dp[i][j][k] = i, j까지 왔을때 k방향을 선택하는 최소값으로 정의하여 풀이를 진행하였다.

 

이때 dp[i][j][0] 은 왼쪽 아래로 오는 방향을 구한것이기 때문에 왼쪽 방향으로 오려면 i-1, j-1 에서 와야 하며 0(왼쪽 대각선)으로 오면 안되기 때문에 1, 2 방향에서 가져와서 최소값을 구해주었다.