[BOJ] 4485 : 녹색 옷 입은 애가 젤다지?
풀이
BFS
엄청 쉬워보이는데 그냥 체크배열을 만들어서 탐색을 하면 더작은값(최소값)으로 갱신을 못한다.
그래서 처음에는 chk배열을 0으로 초기화를 하고,
chk가 0이거나 chk[nx][ny]-arr[nx][ny]>cnt 조건을 만족하면
값을 갱신해나가도록 했다.
하지만 입력값에 0이 들어올 수 있었고, 연속으로 들어오면 무한반복되는 문제가 있다.
그래서 chk를 아주큰수로 초기화 해서 문제를 해결했다.(더적은 값으로만 갱신된다)
그리고 다른 갱신값까지 기다려야 하므로 x==n-1 && y==n-1이면 다음큐로 continue를 했다.
이렇게 하니 176ms가 나왔다.
가만히 생각해보니 항상 최소값으로만 움직이면 x==n-1 && y==n-1일때 break를 할 수 있었다.
항상 최소값으로 먼저 움직이기 위해 큐를 최소힙 우선순위큐로 바꿨다.
그리고 도착시 break시키니까
4ms가 나왔다.
멋져.
아그리고 주석처리되있는부분인
한큐끝날때마다 chk배열만 출력하도록 하는코드로
디버깅했더니 굉장히 편하고 좋았다.
코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cstring>
#include <queue>
using namespace std;
int arr[125][125];
int chk[125][125]; //memo
const int dx[]={-1,0,1,0};
const int dy[]={0,1,0,-1};
int n;
void bfs(){
//(x,y),cnt
priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>> q;
q.push({arr[0][0],{0,0}});
chk[0][0]=arr[0][0];
while(!q.empty()){
int x=q.top().second.first;
int y=q.top().second.second;
int cnt=q.top().first;
q.pop();
if(x==n-1&&y==n-1){
break;
}
for(int dir=0;dir<4;dir++){
int nx=x+dx[dir];
int ny=y+dy[dir]; if(nx>=0&&nx<n&&ny>=0&&ny<n&&(chk[nx][ny]-arr[nx][ny]>cnt)){
q.push({cnt+arr[nx][ny],{nx,ny}});
chk[nx][ny]=cnt+arr[nx][ny];
}
}
/*
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
cout<<chk[i][j]<<' ';
}
cout<<'\n';
}
cout<<'\n';
*/
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n;
int t=1;
while(n!=0){
memset(arr,0,sizeof(arr));
memset(chk,0,sizeof(chk));
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>arr[i][j];
chk[i][j]=10000000;
}
}
bfs();
cout<<"Problem "<<t<<": "<<chk[n-1][n-1]<<'\n';
t++;
cin>>n;
}
return 0;
}
Written on March 29, 2019