Life Engineering
[BOJ 1261] 알고스팟 (C++) 본문
https://www.acmicpc.net/problem/1261
#include <bits/stdc++.h>
#define INF 987654321
using namespace std;
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
class Node{
public:
int y;
int x;
int cost;
Node(int y, int x, int cost){
this->y=y;
this->x=x;
this->cost=cost;
}
};
struct cmp{
bool operator()(const Node &a, const Node &b){ //최소 힙을 위한 비교자
return a.cost>b.cost;
}
};
int main(){
int M, N;
string s;
cin>>M>>N;
string map[N];
priority_queue<Node, vector<Node>, cmp> pq;
int dist[N][M];
for (int i=0; i<N; i++){
cin>>s;
map[i]=s;
}
for (int i=0; i<N; i++){
for (int j=0; j<M; j++){
dist[i][j]=INF;
}
}
dist[0][0]=0;
pq.push(Node(0,0,0));
while (!pq.empty()){
Node now=pq.top();
pq.pop();
if (now.y==N-1 && now.x==M-1){
break;
}
if (now.cost>dist[now.y][now.x]){
continue;
}
for (int i=0; i<4; i++){
int ny=now.y+dy[i];
int nx=now.x+dx[i];
if (ny<0 || nx<0 || ny>=N || nx>=M){
continue;
}
int newcost=(map[ny][nx]=='0')? 0 : 1;
if (dist[ny][nx]>now.cost+newcost){ //작을 경우에만 갱신
dist[ny][nx]=now.cost+newcost;
pq.push(Node(ny,nx,dist[ny][nx]));
}
}
}
cout<<dist[N-1][M-1]<<"\n";
return 0;
}
처음에 봤을때 BFS 문젠가 싶었지만 문제에서 요구하는 조건이 '최소의 벽을 뚫는 경우' 였다. 최단 거리가 아니라.
즉 벽의 개수를 가중치로 해서 다익스트라 알고리즘을 사용하는 문제이다.
벽일 경우엔 cost에 1을 더하고, 빈 방일 경우엔 cost에 0을 더해 가장 최소의 가중치를 가지고 도착점에 도달할 수 있도록 한다.
dist[i]는 출발지에서 i까지 가는데 필요한 뚫어야될 최소의 벽의 개수이다.
dist[i]가 " 현재 지점까지 오는데 필요한 cost+현재 지점에서 다음지점까지 가는데 필요한 cost "보다 크다면 후자의 것으로 갱신하여 우선순위 큐에 넣어준다.
'Problem Solving' 카테고리의 다른 글
[BOJ 4195] 친구 네트워크 (C++) (0) | 2021.08.11 |
---|---|
[BOJ 1976] 여행 가자(C++) (0) | 2021.08.10 |
[BOJ 9202] Boggle (C++) (0) | 2021.07.22 |
[BOJ 1202] 보석 도둑(C++) (0) | 2021.07.22 |
[BOJ 1927] 최소 힙(C++) (0) | 2021.07.22 |