[백준 1261] 알고스팟

https://www.acmicpc.net/problem/1261

1261번: 알고스팟

요구사항

벽을 제일 최소한으로 만나서 제일 오른쪽 밑에 도착하기

 

풀이

다익스트라 알고리즘으로 bfs처럼 풀이한다.

dist[i][j]를 INF으로 저장하고

갱신할 수 있으면 갱신하는 형식으로 푼다

갱신할 수 없다면 최소로 도달하는게 아니다

 

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;
const int INF=0x7fffffff;
int dr[4] = {-1,0,1,0};
int dc[4] = {0,-1,0,1};
int map[101][101];
int dist[101][101];
int n,m;

int main()
{
    cin>>n>>m;
    for(int i=0 ; i < m ; i++){
        for(int j=0 ; j < n ; j++){
            char ch;
            scanf(" %c",&ch);
            if(ch=='1'){
                map[i][j]=1;
            }
            else{
                map[i][j]=0;
            }
            dist[i][j]=INF;
        }
    }
    priority_queue<pair<pair<int,int> ,int>> q;
    dist[0][0]=0;
    q.push({{0,0},0 });
    while(!q.empty()){
        int r = q.top().first.first;
        int c = q.top().first.second;
        int dis = -q.top().second;
        q.pop();
        if(dis>dist[r][c])
            continue;
        for(int i=0 ; i <4 ; i++){
            int nr = r+dr[i];
            int nc = c+dc[i];
            if(nr<0 || nc<0 || nr>=m || nc>=n){
                continue;
            }
            int ndist=dis+map[nr][nc];
            if( dist[nr][nc] > ndist){
                dist[nr][nc]= ndist;
                q.push({{nr,nc},-ndist});
            }
        }
    }
    cout<<dist[m-1][n-1];


}