https://www.acmicpc.net/problem/1445
1445번: 일요일 아침의 데이트
첫째 줄에 숲의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 3보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 숲의 지도가 주어진다. 숲의 지도는 S, F, g, . 만으로 이루어져 있
www.acmicpc.net
[난이도] Gold2
[유형] 다익스트라
[풀이]
cost를 {쓰레기의 위치, 쓰레기에 인접한 위치}의 pair로 두고 다익스트라를 돌려주면 됩니다.
#include <cstdio>
#include <iostream>
#include <functional>
#include <queue>
#include <algorithm>
using namespace std;
struct P{
pair<int,int> g,pos;
};
int N,M,dy[4]={-1,1,0,0},dx[4]={0,0,1,-1},sy,sx,ey,ex;
char board[50][50];
pair<int,int> dist[50][50];
struct cmp{
bool operator()(P& a,P b){
if(a.g.first>b.g.first) return true;
else if(a.g.first==b.g.first) return a.g.second>b.g.second;
return false;
}
};
int main(){
scanf("%d%d",&N,&M);
for(int i=0;i<N;i++)
for(int j=0;j<M;j++) {
scanf(" %c",&board[i][j]);
if(board[i][j]=='S') sy=i,sx=j;
if(board[i][j]=='F') ey=i,ex=j;
dist[i][j]={9e8,9e8};
}
priority_queue<P,vector<P>,cmp> pq;
dist[sy][sx]={0,0};
pq.push({{0,0},{sy,sx}});
while(!pq.empty()){
auto [g,pos] = pq.top(); pq.pop();
auto [y,x] = pos;
if(g!=dist[y][x]) continue;
for(int i=0;i<4;i++){
int ny=y+dy[i],nx=x+dx[i];
if(ny<0||nx<0||ny>=N||nx>=M) continue;
pair<int,int> p = g;
if(board[ny][nx]=='g') p = {g.first+1,g.second};
else if(board[ny][nx]=='.') {
bool ok=0;
for(int j=0;j<4;j++){
int ty=ny+dy[j],tx=nx+dx[j];
if(ty<0||tx<0||ty>=N||nx>=M) continue;
if(board[ty][tx]=='g'){
ok=1;
break;
}
}
if(ok) p = {g.first,g.second+1};
}
if(p<dist[ny][nx]){
dist[ny][nx]=p;
pq.push({p,{ny,nx}});
}
}
}
printf("%d %d",dist[ey][ex].first,dist[ey][ex].second);
}
https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold2/1445.cpp
'Problem-Solving > BOJ' 카테고리의 다른 글
| [BOJ/백준][Gold2] 3687 : 성냥개비 (C++) (0) | 2022.03.27 |
|---|---|
| [BOJ/백준][Gold2] 1781 : 컵라면 (C++) (0) | 2022.03.27 |
| [BOJ/백준][Gold2] 14725 : 개미굴 (C++) (0) | 2022.03.27 |
| [BOJ/백준][Gold2] 9997 : 폰트 (C++) (0) | 2022.03.27 |
| [BOJ/백준][Gold2] 2159 : 케익 배달 (C++) (0) | 2022.03.27 |