[BOJ/Gold 3] 백준 27978 보물 찾기 2(C++)

문제 링크

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

 

문제

건덕이는 지난 보물찾기에서 보물을 찾는 데 성공했다. 이제는 배를 타고 세계 곳곳을 누비며 보물을 찾아 나서는 보물 탐사대가 되었다.

건덕이는 주변 섬들의 지형이 담긴 가로 W칸, 세로 H칸의 지도를 구했다. 지도에는 주변 바다의 지형이 나타나 있다. 바다와 암초로 이루어져 있는데, 배는 암초 위를 지나다닐 수 없다. 지도의 가장 왼쪽 위는 (1, 1), 오른쪽 아래는 (H, W)이다.

건덕이의 배는 매번 인접한 8칸 중 한 곳으로 이동할 수 있다. (r, c)와 인접한 칸은 max(|r − x|, |c − y|) = 1인 (x, y)이다. 안전한 항해를 위해 지도 바깥으로는 나가지 않는다.

바다의 물살이 지도 기준 왼쪽에서 오른쪽으로 빠르게 흐르고 있어서, 물살을 타고 가는 데에는 연료가 들지 않지만, 그 외에는 한 칸당 1의 연료가 소모된다. 예를 들어, 건덕이가 현재 (r, c) 위치에 자리 잡고 있다면 (r − 1, c + 1), (r, c + 1), (r + 1, c + 1)로는 연료 소모 없이 이동할 수 있고, 그 외의 칸으로는 1의 연료를 소모해야 한다.

건덕이의 손에 보물지도가 주어졌다. 보물을 찾기까지 소모해야 하는 연료의 최솟값을 구해 주자!

입력

첫 번째 줄에 보물 지도의 세로 길이 H, 가로 길이 W가 주어진다. (3 ≤ H, W ≤ 500)

두 번째 줄부터 H개의 줄에 걸쳐 지도가 주어진다. 지도는 .#*K 중 하나로만 나타내져 있으며, 각각 바다, 암초, 보물, 배를 의미한다. 배와 보물은 지도에 한 번만 주어진다.

출력

물살을 헤쳐 보물을 찾기까지 소모하는 연료의 최솟값을 출력한다. 도달할 수 없는 경우에는 −1을 출력한다.

예제 입력 1

3 5
....*
K.#..
#...#

예제 출력 1

0

예제 입력 2

3 5
....K
*.#..
#...#

예제 출력 2

4

예제 입력 3

3 3
K..
###
*..

예제 출력 3

-1

알고리즘 분류

• 그래프 탐색

풀이

배의 현재 위치에서 암초가 아닌 모든 칸까지 도달하는 데 필요한 연료의 최솟값을 기록한다.

그리고 보물이 위치한 칸까지 도달하는 데 필요한 연료의 최솟값을 출력한다.

만약 보물이 위치한 칸까지 도달하는 경우가 없다면 -1을 출력한다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#define MAX 501
#define INF 1e9
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int W, H;
string S;
int MAP[MAX][MAX];
pair<int, int> Start, End;
int Visited[MAX][MAX];
int MoveY[8] = { -1,0,1,1,1,0,-1,-1 };
int MoveX[8] = { 1,1,1,0,-1,-1,-1,0 };

void init() {
    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            Visited[i][j] = INF;
        }
    }
}

void input() {
    cin >> H >> W;
    for (int i = 1; i <= H; i++) {
        cin >> S;
        for (int j = 1; j <= W; j++) {
            if (S[j - 1] == '#') {
                MAP[i][j] = -1;
            }
            else if (S[j - 1] == '*') {
                End = make_pair(i, j);
            }
            else if (S[j - 1] == 'K') {
                Start = make_pair(i, j);
            }
        }
    }
}

void settings() {
    queue<pair<pair<int, int>, int> > Q;
    Visited[Start.first][Start.second] = 0;
    Q.push(make_pair(Start, 0));

    while (!Q.empty()) {
        int NowY = Q.front().first.first;
        int NowX = Q.front().first.second;
        int NowC = Q.front().second;
        Q.pop();

        for (int i = 0; i < 3; i++) {
            int NextY = NowY + MoveY[i];
            int NextX = NowX + MoveX[i];
            if ((NextY < 1) || (NextY > H) || (NextX < 1) || (NextX > W)) {
                continue;
            }
            if (MAP[NextY][NextX] == -1) {
                continue;
            }
            if (Visited[NextY][NextX] <= NowC) {
                continue;
            }
            Visited[NextY][NextX] = NowC;
            Q.push(make_pair(make_pair(NextY, NextX), NowC));
        }
        for (int i = 3; i < 8; i++) {
            int NextY = NowY + MoveY[i];
            int NextX = NowX + MoveX[i];
            if ((NextY < 1) || (NextY > H) || (NextX < 1) || (NextX > W)) {
                continue;
            }
            if (MAP[NextY][NextX] == -1) {
                continue;
            }
            if (Visited[NextY][NextX] <= NowC + 1) {
                continue;
            }
            Visited[NextY][NextX] = NowC + 1;
            Q.push(make_pair(make_pair(NextY, NextX), NowC + 1));
        }
    };
}

void find_Answer() {
    if (Visited[End.first][End.second] == INF) {
        cout << "-1\n";
    }
    else {
        cout << Visited[End.first][End.second] << "\n";
    }
}

int main() {
    FASTIO
    init();
    input();
    settings();
    find_Answer();

    return 0;
}