BOJ
BOJ::14461 소가 길을 건너간 이유 7
BOJ Gold 2
BOJ::14461 소가 길을 건너간 이유 7
- Link : BOJ::14461
- Link : JusticeHui
- Level : Gold 2
- tag : dijkstra
시사점
- 배울점이 많은 좋은 문제였습니다.
- 태그로 걸어둔 JusticeHui 님의 블로그에서 좋은 테크닉을 2가지 배웠습니다.
- i행과 j열을 queue에 넣을때 보통 x, y로 따로 따로 넣습니다.
- 둘의 범위가 100 이하 500 이하임에도 불구하고 말입니다.
- 하지만, i * n + j 로 넣고, 역으로 꺼내면 하나의 크기에 둘을 넣을 수 있습니다.
- 다른 한 가지는, 해당 문제에서 제시된 3칸의 이동을 한번에 하는 방법입니다.
- 저는 보통 다른 문제들을 풀듯이 모든 상태를 잘게 쪼개서 접근하였습니다.
- int status[ x ][ y ][ move ] 와 같은 식으로요.
- 하지만 위와 같이 해결하려 하면 시간초과가 발생합니다.
- bool 이라고 생각해도 10^8이나 되기 떄문입니다.
- 따라서, int status[ x ][ y ] 로 해결해보려 하였지만 이도 쉽지 않습니다.
- 문제에 따르면, 갔던 곳을 재방문 해야할 때가 있어야 하고, 이는 이동수에 영향을 받기 떄문입니다.
- 따라서 해당 방법으로는 해결할 수 없습니다.
- hui님은 이를 다음과 같이 해결합니다.
- 하나의 이동으로 3칸을 이동시키는 것입니다.
- 그렇게 생각할 수도 있는 이유는, 3번째마다 값을 더하고, 그 외에는 그냥 이동이기 때문입니다.
- 생각해보면, 3칸을 한번에 이동하는 방법의 수는 16가지밖에 되지 않습니다.
- i행과 j열을 queue에 넣을때 보통 x, y로 따로 따로 넣습니다.
이해(x)
- (0,0)에서 출발하여 (N-1,N-1)까지 가려고 할때, 걸리는 최소 시간을 출력합니다.
- 1초에 상하좌우 인접한 한 칸을 이동할 수 있습니다.
- 또한 3초마다 해당 위치에 있는 수의 시간만큼 시간이 더해집니다.
설계, 손 코딩(x)
- 손으로 중심이 되는 코드를 구현합니다.
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
const int MAXN = 100, inf = 0x3f3f3f;
const int dx[]={-1, 0, 1, 0, -3, 0, 3, 0, -2, -2, -1, -1, 1, 1, 2, 2},
dy[]={0, 1, 0, -1, 0, 3, 0, -3, -1, 1, -2, 2, -2, 2, -1, 1};
using namespace std;
int n, t;
int a[MAXN][MAXN];
int dist[MAXN][MAXN];
priority_queue<pair<int,int> > pq; // sum(min), idx
void input(){
cin >> n >> t;
rep(i, 0, n) rep(j, 0, n) cin >> a[i][j];
fill(&dist[0][0], &dist[0][0] + MAXN*MAXN, inf);
}
bool over(int x, int y){ return (x<0 || y<0 || x>=n || y>=n);}
void dijkstra(){
int ans = inf;
dist[0][0] = 0;
pq.push({0, 0});
while(!pq.empty()){
int cost = -pq.top().first;
int x = pq.top().second / n;
int y = pq.top().second % n;
pq.pop();
if(dist[x][y] != cost) continue; // dijkstra
int toN = (n-1 - x) + (n-1 - y);
if(toN <= 2){
ans = min(ans, cost + toN * t);
}
rep(i, 0, 16){
int nx = x+dx[i], ny = y+dy[i];
if(over(nx, ny)) continue;
int ncost = cost + a[nx][ny] + t * 3;
if(dist[nx][ny] > ncost){
dist[nx][ny] = ncost;
pq.push({-ncost, nx * n + ny});
}
}
}
cout << ans << endl;
}
void process(){
input();
dijkstra();
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
process();
return 0;
}
최초 접근하였던 TLE 코드입니다.
#include<bits/stdc++.h>
#define endl '\n'
#define rep(i,a,b) for(int i=a;i<b;i++)
typedef long long ll;
const int MAXT = 1000*1000;
const int MAXN = 100;
const int MAX_aij = 100*1000;
const int inf = 0x3f3f3f3f;
const int dx[]={-1, 0, 1, 0}, dy[]={0, 1, 0, -1};
int n, et, ex, ey;
struct cell{int x; int y; int mv; int sum_aij;
bool operator<(const struct cell & t)const{
return 1LL * mv * et + sum_aij > 1LL * t.mv * et + t.sum_aij;
}
};
using namespace std;
int a[MAXN][MAXN];
int seen[MAXN][MAXN][ MAXN * MAXN ]; // [0,10^9]
priority_queue<cell> pq;
void input(){
cin >> n >> et;
rep(i, 0, n) rep(j, 0, n) cin >> a[i][j];
fill(&seen[0][0][0], &seen[0][0][0] + MAXN*MAXN*MAXN*MAXN, inf);
ex = n-1, ey = n-1;
}
bool over(int x, int y){return (x<0 || y<0 || x>=n || y>=n);}
void bfs(){
ll ans = inf;
pq.push({0, 0, 0, 0});
seen[0][0][0] = 0;
while(!pq.empty()){
int x = pq.top().x, y = pq.top().y, mv = pq.top().mv, sum_aij = pq.top().sum_aij;
pq.pop();
if( x == ex && y == ey){
ans = min(ans, 1LL * mv * et + sum_aij );
cout << ans << endl;
return;
}
rep(d, 0, 4){
int nx = x+dx[d], ny = y+dy[d], nmv = mv+1, nsum_aij = sum_aij;
if(over(nx, ny)) continue;
if(nmv %3 ==0)
nsum_aij += a[nx][ny];
if(seen[nx][ny][nmv] > nsum_aij){
seen[nx][ny][nmv] = nsum_aij;
pq.push({nx, ny, nmv, nsum_aij});
}
}
}
}
void process(){
input();
bfs();
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
process();
return 0;
}