[백준 1445] 일요일 아침의 데이트

문제

www.acmicpc.net/problem/1445

 

알고리즘

다익스트라

 

풀이

쓰레기와 쓰레기 근처를 최소로 하여 도착지까지 도착해야하는 문제입니다.

 

다익스트라에서 사용하는 $dist$배열을 pair형태로 사용합니다. first와 second는 각각 지나간 쓰레기와 쓰레기 근처를 지나간 횟수를 의미합니다. pair값들의 비교를 위해 $comp$를 함수를 작성했습니다. 다른 부분은 일반적인 다익스트라와 동일합니다.

 

코드

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
using namespace std;

const int dy[4] = { 1, -1, 0, 0 };
const int dx[4] = { 0, 0, 1, -1 };
typedef tuple<int, int, int, int> tp;
typedef pair<int, int> pii;

priority_queue<tp, vector<tp>, greater<tp>> pq;

int N, M, sy, sx, fy, fx;
int board[50][50];
pii dist[50][50];

bool comp(const pii& a, const pii& b) {
    if (a.first == b.first)
        a.second < b.second;
    return a.first < b.first;
}
bool inr(int y, int x) {
    return 0 <= y && y < N && 0 <= x && x < M;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> N >> M;

    rep(i, N) rep(j, M) {
        char x;
        cin >> x;
        if (x == 'g') {
            board[i][j] = 1;
            rep(k, 4) {
                int ny = i + dy[k];
                int nx = j + dx[k];
                if (!inr(ny, nx))
                    continue;
                if (board[ny][nx] == 0) {
                    board[ny][nx] = 2;
                }
            }
        } else if (x == 'F') {
            fy = i;
            fx = j;
            board[i][j] = 3;
        } else if (x == 'S') {
            sy = i;
            sx = j;
        }
    }
    memset(dist, 0x3f, sizeof(dist));
    dist[sy][sx] = { 0, 0 };
    pq.emplace(0, 0, sy, sx);

    while (!pq.empty()) {
        auto [g, n, y, x] = pq.top();
        pq.pop();

        if (comp(dist[y][x], { g, n })) {
            continue;
        }
        if (board[y][x] == 3)
            break;

        rep(i, 4) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (!inr(ny, nx))
                continue;
            int vf = (board[ny][nx] == 1 ? 1 : 0);
            int vs = (board[ny][nx] == 2 ? 1 : 0);

            if (comp({ g + vf, n + vs }, dist[ny][nx])) {
                dist[ny][nx].first = g + vf;
                dist[ny][nx].second = n + vs;
                pq.emplace(dist[ny][nx].first, dist[ny][nx].second, ny, nx);
            }
        }
    }
    auto [a, b] = dist[fy][fx];
    cout << a << ' ' << b << '\n';

    return 0;
}