[C++] 백준 22255번 : 호석사우루스

🔗 문제

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

 

✏️ 풀이

 

완전탐색으로 풀기에는 너무 많은 경우의 수가 생긴다는 것을 알 수 있다.

이 문제는 다익스트라 문제다.

DP[i][j]를 시작점부터 (i, j)에 도달할때까지 받은 총 충돌량의 최소값으로 정의하고, 기존 DP보다 값이 작을 때만 그 방향으로 탐색을 해주게 되면 경우의 수가 가지치기 되므로 시간 안에 문제를 풀 수 있다.

 

문제 포인트

 

#매 이동 시 마다 움직일 수 있는 방향이 다르다.

이동 횟수(k)가 갈 수 있는 방향을 결정한다.

3k, 3k+1, 3k+2는 k%3으로 바로 바꿔 사용할 수 있다.

• k%3==0 : 상하좌우
• k%3==1 : 상하좌우
• k%3==2 : 상하좌우

상하좌우를 변수로 선언해두고 range를 설정해주어서 이동 가능한 방향을 설정해주었다.

pii setRange(const int k)
{		
    if(k == 0) return make_pair(0, 4);
    if(k == 1) return make_pair(0, 2);
    if(k == 2) return make_pair(2, 4);
}

 

 

#같은 방을 여러 번 들어가면, 들어갈 때마다 같은 충격량을 받게 된다.

 

같은 방을 중복해서 방문할 수 있다면, 

우리가 진행할 수 있는 3가지 방법인 mod마다 서로 dp[i][j]를 가질 수가 있다. 

 

즉,  3k+1, 3k+2, 3k+3 (mod = {1, 2, 3})일 때 모두 다른 총 충격량을 가질 수 있다는 것을 의미한다.

그렇기 때문에 dp[mod][i][j]로 확장하여서 문제를 풀어주면 된다.

 

 

🤔 궁금한 점

사실 3차원배열을 처음부터 생각한게 아니다.

2중와일문을 돌려 이동횟수 K를 체크하고, 평범하게 2차원배열로 풀었다가 답이 안 나와서 부랴부랴 수정을 해서 맞출 수 있었다.

 

처음부터 3차원배열으로 해야겠다는 생각은 어떻게!? 어느 포인트에서 바로 주워갈 수 있을까?!

 

 

💾  소스

#include <iostream>
#include <vector>
#include <queue>
#define MAX 101
#define INF 1e9

using namespace std;

typedef pair<int, int> pii;

const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};

int N, M;
int startX, startY, endX, endY;

vector<vector<int>> grid;
vector<vector<vector<int> > > dp;

struct info
{
    info(int x, int y, int cost, int k) : x(x), y(y), cost(cost), k(k) {}

    int x, y, cost, k;

    bool operator>(const info& o) const
    {
        return cost > o.cost;
    }
};

pii setRange(const int k)
{		
    if(k == 0) return make_pair(0, 4);
    if(k == 1) return make_pair(0, 2);
    if(k == 2) return make_pair(2, 4);
}

int getAnswer()
{
    priority_queue<info, vector<info>, greater<info>> pq;
    pq.push({startX-1, startY-1, 0, 1});

    while(!pq.empty())
    {
        info top = pq.top(); pq.pop();
        
        int mod = top.k % 3;
        pii range = setRange(mod);

        for(int d=range.first; d<range.second; ++d)
        {
            int x = top.x + dx[d];
            int y = top.y + dy[d];

            if (x < 0 || y < 0 || x >= N || y >= M) continue;
            if (grid[x][y] == -1) continue;
            
            if (x==endX-1 && y==endY-1) 
                return top.cost; 

            int next_cost = top.cost + grid[x][y];
            if (next_cost < dp[mod][x][y])
            {
                dp[mod][x][y] = next_cost;
                pq.push({x, y, dp[mod][x][y], top.k+1});
            }
        }
    }
    
    return -1;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);
    
    cin >> N >> M;
    cin >> startX >> startY >> endX >> endY;

    grid.resize(N, vector<int>(M));
    dp.resize(3, vector<vector<int> >(N, vector<int>(M, INF)));

    for(int i=0; i<N; ++i)
        for(int j=0; j<M; ++j)
            cin >> grid[i][j];
    
    cout << getAnswer();

    return 0;
}