[백준/c++] BOJ 27978 - 보물 찾기 2

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

27978번: 보물 찾기 2

 

문제 설명

WxH 지도가 있다. 지도는 ., #, *, K로 이루어져 있다. 각각 바다, 암초, 보물, 배를 의미하며 배는 암초 위를 지나가지 못한다. 매번 인접한 8칸 중 한 곳으로 이동할 수 있는데, 현재 (r, c) 위치에 자리 잡고 있다면 (r - 1, c + 1), (r, c + 1), (r + 1, c + 1)로는 연료 소모 없이 이동할 수 있다. 그 외의 칸으로는 1의 연료를 소모해야 한다. 보물을 찾을 때까지 소모해야 하는 연로의 최솟값을 구한다.

H, W (3 <= H, W <= 500)

해결

연료 소모 없이 이동할 수 있는 칸과, 소모하며 이동하는 칸을 각각 고려해 주어야 한다.

 

연료 소모 없이 이동할 수 있는 칸은 visited 값을 늘리지 않고 bfs 돌아 준다.

먼저 도착하지 않아도 연료를 소모하지 않고 도착하면 연료 소모를 최소한으로 하고 들어올 수 있으므로, 도착지를 만났다고 바로 return 해 주면 안 된다.

 

이외에 딱히 특별한 점은 없다.

코드

#include<bits/stdc++.h>
#define x first
#define y second
#define INF 1e9
using namespace std;

int n, m;
pair<int, int> start;
pair<int, int> bomul;
int visited[501][501];
char board[501][501];
int dx[8] = { -1, 0, 1, 1, 1, 0, -1, -1 }, dy[8] = { 1, 1, 1, 0, -1, -1, -1, 0 };

int range_over(int nx, int ny) {
    return nx < 0 || ny < 0 || nx >= n || ny >= m;
}

void bfs() {
    queue<pair<pair<int, int>, int>> q;
    q.push({ start, 0});
    visited[start.x][start.y] = 0;

    while (!q.empty()) {
        auto cur = q.front(); q.pop();
        for (int dir = 0; dir < 3; dir++) {
            int nx = cur.x.x + dx[dir], ny = cur.x.y + dy[dir];
            if (range_over(nx, ny) || visited[nx][ny] <= cur.y || board[nx][ny] == '#') continue;
            visited[nx][ny] = cur.y;
            q.push({ {nx, ny}, cur.y });
        }
        for (int dir = 3; dir < 8; dir++) {
            int nx = cur.x.x + dx[dir], ny = cur.x.y + dy[dir];
            if (range_over(nx, ny) || visited[nx][ny] <= cur.y + 1|| board[nx][ny] == '#') continue;
            visited[nx][ny] = cur.y + 1;
            q.push({ {nx, ny}, cur.y + 1});
        }
    }
}

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

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            visited[i][j] = INF;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> board[i][j];
            if (board[i][j] == 'K') {
                start.x = i, start.y = j;
            }
            else if (board[i][j] == '*') {
                bomul.x = i, bomul.y = j;
            }
        }
    }
    bfs();
    if (visited[bomul.x][bomul.y] == INF) cout << -1;
    else cout << visited[bomul.x][bomul.y];
}