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

1. 개요

 안녕하세요. 이번 문제의 유형은 2차원 배열에 다익스트라 알고리즘을 응용한 문제였습니다. 문제를 읽고 상태값을 거리 배열에 저장하는 방법을 사용하는 너비우선탐색 응용문제일 거라고 생각하고 풀이했다가 런타임 에러에 막혀 알고리즘 유형을 까고 나서야 풀이할 수 있었습니다. 무의식적으로 2차원 배열은 너비우선탐색 또는 dfs를 응용한 dp문제라고 생각하고 풀이한 것 같습니다. 이 문제를 푼 오늘이 일요일인데 우연히 문제 제목에도 일요일이 있었네요. 어쩌라고요? 그냥 그렇다고요 반박 시 니 얼굴이고요

 

2. 문제 풀이

 우선 배열을 탐색하면서 필요한 데이터 정보를 파악해 봅시다. "쓰레기칸과 인접한 칸을 지나가는 경우", "쓰레기칸을 이동하는 경우", "현재 위치 정보 (x, y)"와 같은 정보가 필요합니다. 다익스트라를 위한 우선순위 큐에는 이러한 4개의 데이터가 저장될 필요가 있습니다. 지문을 잘 읽었으면 문제가 없을 테지 다들 어려워하는 부분이 있습니다. 바로 "쓰레기칸과 인접한 칸을 지나가는 경우"입니다.  "쓰레기칸과 인접한 칸을 지나가는 경우"를 만족하기 위해서는 빈칸('.')이면서 인접한 상화좌우 칸에 쓰레기 칸이 있는 경우입니다. 따라서 이러한 경우에만 카운트를 해주시면 문제 풀이에 어려움은 없습니다.

 이제 데이터를 파악했다면 다익스트라를 구성하는 과정은 해당 알고리즘을 알고 있다는 가정하에 매우 쉽습니다. 저 같은 경우 아래와 같이 선언하여 다익스트라를 구현했습니다.

// pair<int, int> d[n][m]
// (n, m) 위치에 쓰레기 칸을 x번 지나가고, 쓰레기칸 옆을 y번 지나갔다.
// d[n][m] = { x, y }
vector<vector<pair<int, int>> d(n, vector<pair<int, int>>(m, {INF, INF});

// 우선 순위 큐
using tii = tuple<pair<int, int>, int, int>; // { d[x][y], x, y }
priority_queue<tii, vector<tii>, greater<tii>> pq;

 INF는 1e9 + 7을 저장합니다. 이후 다익스트라는 쓰레기 칸을 지나는 경우, 쓰레기칸과 인접한 칸을 지나는 경우, 빈칸을 지나는 경우에 따라 적절하게 거리 배열값을 갱신하여 진행하시면 됩니다.

 

3. 코드 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';

const int INF = 1e9 + 7;
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };

int n, m;
string board[55];
int sx, sy, ex, ey;

int main() {
    fastio(nullptr, false);

    cin >> n >> m;
    for(int i = 0; i < n; i++) {
        cin >> board[i];
    }

    vector<vb> exists_nearby(n, vb(m));
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(board[i][j] == 'g') {
                for(int dir = 0; dir < 4; dir++) {
                    int nx = i + dx[dir];
                    int ny = j + dy[dir];
                    if(0 <= nx && nx < n && 0 <= ny && ny < m) {
                        exists_nearby[nx][ny] = 1;
                    }
                }   
            }
            else if(board[i][j] == 'S') {
                sx = i;
                sy = j;
            }
            else if(board[i][j] == 'F') {
                ex = i;
                ey = j;
            }            
        }
    }

    using tii = tuple<pi, int, int>;
    vector<vpi> d(n, vpi(m, {INF, INF}));
    priority_queue<tii, vector<tii>, greater<tii>> pq;

    pq.push({d[sx][sy] = {0, 0}, sx, sy});
    while(sz(pq)) {
        auto [cur, cx, cy] = pq.top(); pq.pop();
        if(cur != d[cx][cy]) continue;  
        for(int dir = 0; dir < 4; dir++) {
            int nx = cx + dx[dir];
            int ny = cy + dy[dir];
            if(0 <= nx && nx < n && 0 <= ny && ny < m) {
                pi nxt = cur;
                if(board[nx][ny] == 'g') {
                    nxt.X++;
                }
                else if(board[nx][ny] == '.' && exists_nearby[nx][ny]) {
                    nxt.Y++;
                }
                if(d[nx][ny] > nxt) {
                    pq.push({d[nx][ny] = nxt, nx, ny});
                }
            }
        }
    }    

    cout << d[ex][ey].X << ' ' << d[ex][ey].Y;    
}

 

4. 제출 결과