백준 27978 - 보물 찾기 2 (C++)

문제

• 문제 링크

  
   BOJ 27978 - 보물 찾기 2 
  

• 문제 요약

$H * W$ 크기의 맵이 주어진다.
배에서부터 보물까지 이동하는 데에 드는 최소 연료 소모량을 구해보자.

• 제한

TL : $1$ sec, ML : $512$ MB




$3 ≤ H, W ≤ 500$

$1 ≤ C_i ≤ 10^9$

알고리즘 분류

• 그래프 이론(graphs)
• 다익스트라(dijkstra)

풀이

문제의 정의에 따라
임의의 위치에서 오른 쪽으로 이동할 때 즉, $x$의 좌표가 증가할 때 가중치를 $0$ 으로 두고 나머지 $5$개의 방향에 대해선 가중치를 $1$로 두자.

구현 상 편의를 위해 $($↗, →, ↘$)$에 해당하는 이동을 한 곳으로 몰아주고$( d[5], d[6] , d[7] )$ 인덱스 상의 비교$( i < 5 )$ 를 통해 가중치를 구해 주었다.

이외에 크게 어려울만한 사항은 없으므로..
나머지는 $bfs$를 이용하던, 다익스트라를 이용하던 편한데로 구현해주면 되겠다.

전체 코드

#include<bits/stdc++.h>
using namespace std;
 
int dy[]{ -1, -1, 0, 1, 1, -1, 0, 1 }, dx[]{ 0, -1, -1, -1, 0, 1, 1, 1 };
vector <vector<int>> D(501, vector <int>(501, 1e9));
priority_queue <tuple<int, int, int>> Q;
char M[501][501];
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int h, w, py{}, px{}; cin >> h >> w;
    for (int i(1); i <= h; i++)
        for (int j(1); j <= w; j++)
            if (cin >> M[i][j]; M[i][j] == 'K') D[i][j] = 0, Q.push({ 0, i, j });
            else if (M[i][j] == '*') py = i, px = j;
    while (Q.size())
    {
        auto [a, b, c](Q.top()); Q.pop();
        if (-a <= D[b][c])
            for (int i{}; i < 8; i++)
            {
                int y(b + dy[i]), x(c + dx[i]);
                if (y && x && y <= h && x <= w && M[y][x] ^ '#')
                    if (int d((i < 5) - a); d < D[y][x])
                        D[y][x] = d, Q.push({ -d, y, x });
            }
    }
    cout << (D[py][px] < 1e9 ? D[py][px] : -1);
}

comment

끝