소가 길을 건너간 이유 7
문제 해석
베시가 존의 집에 도착하는 최소 시간을 구하는 문제입니다.
소 베시는 한 목초지에서 상하좌우로 인접한 다른 목초지로 이동할 수 있고, 길을 건너는데 T초의 시간이 걸립니다.
또한, 길을 세번 건널 때마다 목초지에 있는 풀을 먹어야 합니다.
목초지마다 풀을 먹는데 걸리는 시간이 다릅니다.
설계(20)
최소비용으로 {N-1,N-1}에 도착하는 다익스트라 알고리즘 활용 문제입니다.
길을 세번 건너는 것을 반복하기 때문에 dist[MAXN][MAXN][3] 3차원 배열을 이용합니다.
길을 세번째 건널 경우, 해당 좌표의 시간을 더해주는 방식으로 진행합니다.
이동하는 시간 + 풀을 먹는 시간을 최소화하는 좌표를 우선순위로 한 뒤 진행합니다.
구현(30)
코드
#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 100
#define INF 987654321
struct node{
int x,y,cnt,time;
bool operator <(const node& a)const{
return a.time < time;
}
};
priority_queue<node> pq;
int dist[MAXN][MAXN][3];
int arr[MAXN][MAXN];
int N,t;
int dx[] = {0,0,1,-1};
int dy[] ={1,-1,0,0};
int dijkstra(){
pq.push({0,0,0,0});
dist[0][0][0] = 0;
while (!pq.empty()){
int x = pq.top().x;
int y = pq.top().y;
int cnt = pq.top().cnt;
int time = pq.top().time;
pq.pop();
if (x == N-1 && y == N-1) {
int res = INF;
for (int i = 0 ; i <3; i++){
if (dist[N-1][N-1][i]==-1) continue;
res = min(res,dist[N-1][N-1][i]);
}
return res;
}
for (int k = 0; k< 4;k++){
int nx= x + dx[k];
int ny = y + dy[k];
if (nx < 0 || ny < 0 || nx>=N || ny>=N) continue;
int next_time = dist[x][y][cnt]+t;
if (cnt ==2) next_time += arr[nx][ny];
if (dist[nx][ny][(cnt+1)%3]==-1 || dist[nx][ny][(cnt+1)%3]>next_time){
dist[nx][ny][(cnt+1)%3]=next_time;
pq.push({nx,ny,(cnt+1)%3,next_time});
}
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N >> t;
memset(dist,-1,sizeof(dist));
for (int i = 0;i<N; i++){
for (int j=0;j<N;j++){
cin >> arr[i][j];
}
}
cout << dijkstra();
return 0;
}
디버깅
처음에 세번째 길에 도착한 경우와 아닌 경우 두개로 나누어서 상태를 표현하려고 하였으나, 로직이 맞지 않았습니다.
따라서 길을 건넌 횟수를 상태로 표현하는 방식으로 변경하였습니다.
제출결과
4 ms
마무리
다익스트라 알고리즘을 활용하는 문제였습니다.
상태를 표현하는 아이디어가 약간 특이한 구조로 재밌는 문제인 것 같습니다.