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

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

1445번: 일요일 아침의 데이트

입력된 맵을 기준으로, 'g'가 놓인칸은 10000, 'g'가 인접해있는 칸은 1, 그외에는 0으로 가중치 배열을 갱신해둔다.

2차원 배열을 1차원 index로 바꾸고, 가중치 배열을 이용해 그래프를 만들어주고, 다익스트라를 돌린다.

최종 cost를 10000으로 나눈 몫이 쓰레기를 지나는 경우의 수이고, 10000으로 나눈 나머지가 쓰레기 옆을 지나는 경우.

---

#include <bits/stdc++.h>

using namespace std;

#ifdef ONLINE_JUDGE

constexpr bool local = false;

#else

constexpr bool local = true;

#endif

using ll = long long;

using pi = pair<ll, ll>;

constexpr int MAX_N = 2501, INF = (int)1e9;

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

int n, m, dst[MAX_N + 1], cost[55][55];

char a[55][55];

typedef struct {

    int idx, cost;

} state;

vector<state> adj[MAX_N + 1];

void dijkstra(int s) {

    auto cmp = [&](state& A, state& B) -> bool { return A.cost > B.cost; };

    priority_queue<state, vector<state>, decltype(cmp)> q(cmp);

    q.push({s, 0});

    fill(dst, dst + MAX_N + 1, INF);

    dst[s] = 0;

    while (!q.empty()) {

        state cur = q.top();

        q.pop();

        if (cur.cost > dst[cur.idx]) continue;

        for (auto& nxt : adj[cur.idx]) {

            if (dst[nxt.idx] > dst[cur.idx] + nxt.cost) {

                dst[nxt.idx] = dst[cur.idx] + nxt.cost;

                q.push({nxt.idx, dst[nxt.idx]});

            }

        }

    }

    return;

}

int c(int y, int x) { return y * m + x; }

int main(void) {

    if (!local) ios_base::sync_with_stdio(0), cin.tie(0);

    cin >> n >> m;

    int i, j, s, e;

    for (i = 0; i < n; i++)

        for (j = 0; j < m; j++) {

            cin >> a[i][j];

            if (a[i][j] == 'S')

                s = c(i, j);

            else if (a[i][j] == 'F')

                e = c(i, j);

        }

    for (i = 0; i < n; i++)

        for (j = 0; j < m; j++) {

            if (a[i][j] == 'g') {

                cost[i][j] = 10000;

                continue;

            } else if (a[i][j] == '.' && cost[i][j] == 0) {

                for (int dir = 0; dir < 4; dir++) {

                    int y = i + dy[dir];

                    int x = j + dx[dir];

                    if (y < 0 || x < 0 || y >= n || x >= m) continue;

                    if (a[y][x] == 'g') {

                        cost[i][j] = 1;

                        break;

                    }

                }

            }

        }

    for (i = 0; i < n; i++)

        for (j = 0; j < m; j++) {

            for (int dir = 0; dir < 4; dir++) {

                int y = i + dy[dir];

                int x = j + dx[dir];

                if (y < 0 || x < 0 || y >= n || x >= m) continue;

                adj[c(i, j)].push_back({c(y, x), cost[y][x]});

            }

        }

    dijkstra(s);

    cout << dst[e] / 10000 << ' ' << dst[e] % 10000;

    return 0;

}

---