[BOJ]백준 1445번: 일요일 아침의 데이트(C++)/Dijkstra

www.acmicpc.net/problem/1445

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

오늘부터 제일 싫어하는 위인 1위: 다익스트라

일요일 아침의 데이트 문제는 좌표를 빈칸 / 쓰레기 칸 / 쓰레기 근처 칸으로 분류해서 최대한 쓰레기 근처를 피해서 목표 지점까지 도달해야 하는 문제이다

처음에 보았을 때는 좌표에 가중치를 두면 되겠다 -> 그러면 쓰레기 칸은 2 & 쓰레기 근처 칸은 1 정도로 놓으면 되겠지?라고 생각했는데 틀렸다

극단적으로 생각하면 형택이는 쓰레기 근처 칸을 n*n번 지나는 것 보다 쓰레기 1칸을 지나는 것을 더 싫어하기 때문에 쓰레기 칸의 value는 그러한 조건을 고려해줘야 하는 것이다

따라서 빈칸 = 0, 쓰레기 옆 칸 = 1, 쓰레기 칸 = 충분히 큰 값으로 설정해주고 다익스트라 알고리즘으로 최단 비용 및 경로를 구해주었다

최단경로는 다익스트라 알고리즘의 실행 도중 current 좌표에 prev좌표를 저장해주는 방식으로 사용했다

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define pip pair<int,point>    //<distance, 좌표>를 저장할 pair
#define INF 987654321
#define garbage 50000          //쓰레기를 지나갈 때의 weight(모든 좌표를 거쳐 쓰레기 주변을 지나는 것 보다 커야함)
#define size 55
using namespace std;

typedef struct { int x, y; }point;
typedef struct {
    bool operator()(pip a, pip b) {
        return a.first > b.first;
    }
}cmp;

int map[size][size];
int n, m;
int dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 };

bool safe(int x, int y) { return x >= 0 && x < m && y >= 0 && y < n; }

pair<int,int> dijkstra(point src,point snk) {
    int dist[size][size];    //minimum distance를 저장할 배열
    point prev[size][size];    //dijkstra를 수행한 뒤 각 좌표의 이전 좌표를 저장할 배열
    bool visit[size][size] = { 0 };    //방문체크 배열
    point nil = { -1,-1 };
    priority_queue<pip, vector<pip>, cmp> pq;    //<distance, point>의 형태로 dijkstra priority queue를 생성

    fill(&dist[0][0], &dist[n + 1][m], INF);
    fill(&prev[0][0], &prev[n + 1][m], nil);

    dist[src.y][src.x] = 0;
    pq.push(make_pair(0, src));

    while (!pq.empty()) {
        point cur = pq.top().second;
        pq.pop();
        if (visit[cur.y][cur.x])continue;

        visit[cur.y][cur.x] = 1;
        for (int i = 0; i < 4; i++) {
            int nx = cur.x + dx[i], ny = cur.y + dy[i];
            if (!safe(nx, ny)||visit[ny][nx])continue;
            if (dist[cur.y][cur.x] + map[ny][nx] < dist[ny][nx]) {    //dijkstra를 통해 최단거리를 갱신시킴
                dist[ny][nx] = dist[cur.y][cur.x] + map[ny][nx];
                point next = { nx,ny };
                pq.push(make_pair(dist[ny][nx], next));
                prev[ny][nx] = cur;    //next의 이전 좌표를 현재 좌표로 저장해주면 최단거리로 가는 실제 경로를 구할 수 잇음
            }
        }
    }

    pair<int, int> cost=make_pair(0,0);
    point path = prev[snk.y][snk.x];    //목적지에서 재귀적으로 prev 좌표로 계속 이동
    while (!(path.x == -1 && path.y == -1)) {    //source 좌표는 (-1,-1)이 저장되어있음
        int c = map[path.y][path.x];
        if (c == 1)cost.second++;    //쓰레기 옆길일경우 count
        else if (c == garbage)cost.first++;    //쓰레기일 경우 count
        path = prev[path.y][path.x];        //현재 좌표의 prev로 이동 
    }

    return cost;    //최종 cost 반환
}

int main() {
    point src, snk;
    cin >> n >> m;

    /*
    처음에는 weight 가중치 차이에 대해 생각 못 하고 쓰레기 - 2 / 쓰레기 옆 길 - 1로 두면 되겠다고 생각했으나
    그러면 쓰레기 옆 길 * 2 = 쓰레기가 되기 때문에 우선순위를 정확하게 하기 위해서는
    N*N개의 쓰레기 옆 길을 거치는 cost < 1개의 쓰레기를 거치는 cost
    로 해줌
    */
    for(int i=0;i<n;i++)
        for (int j = 0; j < m; j++) {
            char c;
            cin >> c;
            switch (c) {
            case 'g':
                map[i][j] = garbage;    //쓰레기일 경우 해당 좌표의 weight를 설정해줌
                break;
            case 'S':        //시작 좌표
                src = { j,i };
                break;
            case 'F':        //목적 좌표
                snk = { j,i };
                break;
            }
        }

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            if (map[i][j] != garbage)continue;
            for (int k = 0; k < 4; k++) {
                int nx = j + dx[k], ny = i + dy[k];
                if (!safe(nx, ny) || map[ny][nx])continue;
                map[ny][nx] = 1;    //쓰레기 옆 길의 weight를 1로 설정
            }
        }

    map[src.y][src.x] = map[snk.y][snk.x] = 0;

    pair<int, int> ans = dijkstra(src, snk);
    cout << ans.first << " " << ans.second;
    return 0;
}