백준 1261 알고스팟: bfs와 caching 쓰는 문제 c++

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

1261번: 알고스팟

사실 이 문제는 분류가 다익스트라 알고리즘으로 분류되어있었는데, 그 알고리즘에 대해서 몰라도 풀수 있다.

전형적인 bfs문제는 아니고 다이나믹 프로그래밍의 캐시 개념만 조금 쓰면 풀 수 있다.

 

어떻게 보면 최단 경로 문제이기 때문에 (빙빙 돌아가면서 벽을 부숴가면서 미로를 탐색하진 않을것 아닌가?) bfs를 쓰는 것은 당연한 것이고,

그렇다면 caching은 어떻게 적용할 것인가?

우선 2차원 dp 배열을 만든다. 각각의 원소는 적당히 큰값으로 초기화를 해주고,

첫 dp[0][0] = 0으로 초기화를 한 이후에, map에서 원소의 값이 0이냐 1이냐를 파악한 후, dp값을 갱신해 가면서, 만약 갱신이 되었다면 그 경우에만 다시 bfs를 돌리면 된다. 이미 최소의 dp값이 있는데 그것보다 더 큰 값을 들고 오면 그 경로는 더 탐색을 안해도 되기 때문이다.

 

<소스 코드> 

#include <iostream>
#include <queue>
#include <string>
using namespace std;
int n,m,answer;
int map[100][100];
int dp[100][100];
 
int dy[4] = {1,-1,0,0};
int dx[4] = {0,0,1,-1};
 
void bfs(int a, int b){
    queue<pair<int,int>> q;
    q.push(make_pair(a,b));
    dp[a][b]=0;
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
//        cout<<x<<" "<<y<<" "<<dp[y][x]<<"\n";
        q.pop();
 
        for(int i=0; i<4;i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx>=0 && ny>=0 && nx < m && ny<n){
                if(map[ny][nx]==0){
                    if(dp[ny][nx]>dp[y][x]){
                        dp[ny][nx]=dp[y][x];
                        q.push(make_pair(nx,ny));
                    }
                }
                else if (map[ny][nx]==1){
                    if(dp[ny][nx]>dp[y][x]+1){
                        dp[ny][nx]=dp[y][x]+1;
                        q.push(make_pair(nx,ny));
                    }
                }
            }
        }
    }
 
 
}
int main(void){
    answer = 999999999;
    cin>>m>>n; //m이 가로길이 n이 세로길이
    for(int i=0; i<n; i++){
        string s;
        cin>>s;
        for(int j=0; j<m; j++){
            map[i][j] = s[j]-'0';
            dp[i][j] = 999999999;
        }
    }
    bfs(0,0);
    cout<<dp[n-1][m-1];
}