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

문제 링크 : [백준]일요일 아침의 데이트(1445)

문제 설명

N * M 배열에 시작점, 빈칸, 꽃, 쓰레기들이 주어집니다.
시작점에서 꽃까지 가는데, 쓰레기를 최소한으로 지나가며,
쓰레기를 지나가는 횟수가 같은 방법이 여러가지라면 옆으로 지나가는 횟수를 최소한으로 지나가는 횟수를 구하세요.

입력

N(배열의 세로 크기, 1 <= N <= 50)
M(배열의 가로 크기, 1 <= M <= 50)
C_ij(각 칸의 정보, .은 빈칸, S는 시작점, F는 꽃, g는 쓰레기)

6 6
......
g..F..
......
..g...
......
...S.g

출력

0 0

카테고리

#다익스트라

시간 복잡도 상한

O(N² * M²) 보다 좀 더 커도 될 것 같습니다.

해결 방법

1. 2차원 배열에서 위, 아래, 왼쪽, 오른쪽으로 이동 가능한 그래프 처리하는 방식을 사용하면 됩니다.
2. BFS와도 굉장히 비슷하지만, 비용을 구해야 합니다.
3. 비용은 쓰레기를 통과하는 횟수를 우선하고, 다음으로 옆으로 지나가는 횟수를 세면 됩니다.
4. 구조체를 만들고 3을 구현한 compare 함수를 만들어 우선순위 큐에 엣지 정보들을 넣습니다.
5. 다익스트라를 돌리면 최소값을 구할 수 있습니다.

시간복잡도

O(N * M * log(N * M))

코드

#include<cstdio>
#include<queue>
#include<algorithm>
#include<vector>
using namespace std;
typedef pair<int,int>P;
int n,m,d[13][3],i;
priority_queue<P,vector<P>,greater<P>>q;
int main(){
    scanf("%d%d",&n,&m);
    for(;i<n;i++)scanf("%d%d%d",d[i],d[i]+1,d[i]+2);
    d[n][0]=d[n][1]=m;
    q.push({0,0});
    while(!q.empty()){
        P c=q.top();q.pop();
        if(c.second==m){
            printf("%d",c.first);
            break;
        }
        for(i=0;i<=n;i++)if(d[i][0]>=c.second)q.push({d[i][2]+d[i][0]-c.second+c.first,d[i][1]});
    }
}