오랜만에 알고리즘 포스팅을 하네요~~~
개인적으로 이것 저것 공부할게 좀 많아서 ㅠㅠ 포스팅에 소홀했던거 같습니다.
이번에 포스팅할 알고리즘 문제는 백준의 4485 녹색 옷 입은 애가 젤다지? 라는 문제입니다.
문제링크: https://www.acmicpc.net/problem/4485
해당 문제를 풀때 사용한 알고리즘은 bfs입니다.
왜 bfs로 문제를 풀었냐고 이유를 물어보신다면 일단 그래프를 탐색해야 하고 + 상하 좌우이동을 하며 링크가 잃을 수밖에 없는 최소 금액을 찾아야 하기때문입니다...
인접 배열로 bfs 문제를 풀어도 n의 범위가 2~125이기 때문에 O(N^2)로 문제를 풀어도 시간초과가 발생하지 않습니다.
기존에 많이 풀어본 bfs문제랑 조금 다른점이라 하면, 대부분의 bfs문제는 이동할 수 있는 최단거리를 구하는 문제들이 많기 때문에 현재 위치에서 상하좌우를 이동하며 목표지점에 먼저 도착하는것이 최단 거리임을 알수 있지만, 이번에 푸는 문제는 최소금액이기 때문에 목표지점까지 최단거리로 이동하는 것이 최소 비용을 보장하지 않습니다. 따라서 우선순위 큐를 사용해 비용을 기준으로 오름차 정렬을 하여, 목표지점에 먼저 도착했을때 비용이 최소 비용임을 보장하도록 문제를 풀었습니다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int arr[126][126];
int vis[126][126];
int dx[]={0,1,-1,0};
int dy[]={-1,0,0,1};
int n;
int res=987654321;
struct qu{
int x;
int y;
int val;
qu(int a,int b,int c){
x=a;
y=b;
val=c;
}
bool operator <(const qu & b) const{
return val>b.val;
}
};
void bfs(int a,int b,int c)
{
priority_queue<qu>pq;
pq.push(qu(a,b,c));
while(!pq.empty()){
int x=pq.top().x;
int y=pq.top().y;
int val=pq.top().val;
pq.pop();
//도착했을 경우
if(x==n-1&&y==n-1){
res=val;
}
//상하좌우 이동
for(int i=0;i<4;i++){
int nx=x+dx[i];
int ny=y+dy[i];
//범위 초과 x때
if(nx>=0&&nx<n&&ny>=0&&ny<n){
//방문 x때
if(vis[nx][ny]==0){
pq.push(qu(nx,ny,val+arr[nx][ny]));
vis[nx][ny]=1;
}
}
}
}
}
void init(){
for(int i=0;i<126;i++){
fill(arr[i], arr[i]+126, 0);
fill(vis[i], vis[i]+126, 0);
res=987654321;
}
}
int main(){
cin.tie(0);
cout.tie(0);
std::ios::sync_with_stdio(false);
int cnt=0;
while(1){
cin>>n;
if(n==0){
break;
}
cnt++;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>arr[i][j];
}
}
//처음 존재하는 위치 방문 표시
vis[0][0]=1;
bfs(0,0,arr[0][0]);
cout<<"Problem"<<' '<<cnt<<": "<<res<<"\n";
//초기화
init();
}
return 0;
}
