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

 

처음 스터디하다가 배웠을 때 신기했던 문제다

이 문제는 다익스트라르 풀 수 있다!

 

다익스트라로 어떻게 풀어야할까

 

쓰레기는 최대한 안지나고 쓰레기 옆길도 안지나고싶다

그럼 가중치를 쓰레기에는 5000, 옆길은 1을 줘보자!

 

5000을 주는 이유는 나올 수 없는 값을 주기 위해서다

왜냐면 나중에 5000으로 나눌거라서 ㅎㅎ

 

문제를 푸는 방법을 생각해보자!

 

1. 먼저 가중치를 쓰레기는 5000, 쓰레기 4방향으로는 1을 주자

2. 그리고 다익스트라를 통해 목적지까지 간다면 최소비용으로 가는 길을 찾을 것이다

3. 그럼 우선순위는 빈칸-> 쓰레기 옆길 -> 쓰레기가 된다

4. 마지막으로 쓰레기를 지나쳤다면 5000a , 옆길을 지나치면 b라는 가중치가 있을것이다

  => 5000a+b가 될테니 /5000을 한다면 쓰레기, %5000을한다면 옆을 지난 수를 구하기 가능!

 

비슷한 문제로는 아래!

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

1261번: 알고스팟

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

17267번: 상남자

상남자 풀이 

https://sejinik.tistory.com/130

[백준] 17267 상남자

 

소스코드

#include <iostream>
#include <algorithm>
#include <queue>    
#include <cstring>
using namespace std;
int n, m,Sx,Sy,Fx,Fy;
int map[55][55];
int d[55][55];
int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };
 
bool inner(int x, int y) {
    return (0 <= x && x < n && 0 <= y && y < m);
}
 
void changeCost(int x, int y) {
    map[x][y] = 5000;
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (inner(nx, ny) && !map[nx][ny]) map[nx][ny] = 1;
    }
}
 
int main() {
    memset(d, -1, sizeof(d));
    scanf(" %d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            char c; scanf(" %1c", &c);
            if (c == 'S') Sx = i, Sy = j,map[i][j]=-1;
            if (c == 'F') Fx = i, Fy = j,map[i][j]=-1;
            if (c == 'g') changeCost(i, j);
        }
    }
    map[Sx][Sy] = map[Fx][Fy] = 0;
    priority_queue<pair<int, pair<int, int>>> pq;
    pq.push({ 0,{Sx,Sy} });
 
    while (!pq.empty()) {
        int cost = -pq.top().first;
        int x = pq.top().second.first;
        int y = pq.top().second.second;
        pq.pop();
 
        if (d[x][y] != -1) continue;
        d[x][y] = cost;
 
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (!inner(nx, ny)) continue;
            if (d[nx][ny] != -1) continue;
            int ncost = -cost - map[nx][ny];
            pq.push({ ncost,{nx,ny} });
        }
    }
    printf("%d %d\n", d[Fx][Fy] / 5000, d[Fx][Fy] % 5000);
}