[BOJ-1261]알고스팟

이 문제는 BFS로 풀었는데 DP로 풀어야 한다고 하길래 음... 뭐 DP인것같기도 한데 내가 아직 DP에 대한 정확한 개념이 없나부다;;

뭐 문제를 요약하자면, 1,1 부터 m,n 까지 간다 이때 나는 row, col 로 생각하고 매트릭스라 생각했으니 x y 로 받은 값을 뒤집어서 했다 

1,1 ~ m,n 까지 갈 때 가장 벽을 적게 부시고 이동하는 것을 찾는 것이다. 문제의 input으로 '1' 은 벽, '0' 은 뚫린 길이다.

그러니 1을 가장 적게 만나며 최대한 0인 길로 이동해야한다는 얘긴데...

뭐 처음에 생각부터 BFS로 맵을 탐색해야겠다 라고 생각했었고, 이동 중에 가장 짧은 ? 짧다라그래야 하나 아닏;;; 보다 긴 경로를 만나면 긴경로를 작은 값으로 갱신한다.

(큐에넣은자료)이동했을 시에 주변에 (자신)or (자신+1)보다 큰 값이 생기면 각 값으로 갱신한다. (mov 벡터배열을)

큐에 넣고 값을 갱신하는 방식으로 하였다. 

자신 / 자신+1 은 

① 이동 시에 벽이 아닌 것 (0) 

② 이동 시에 벽인 상태 (1)

로 큐에 갱신을 위해 집어 넣는다. 

음.... 위의 방식대로 BFS 탐색을 하며 mov 배열 값을 갱신하며 마지막 값인 mov [m-1][n-1] 을 출력했다.

#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
typedef vector<int> VI;
typedef vector<VI> VVI;
const int INF = 0x00FFFFFF;
struct info{
    int r;
    int c;
 
    info(int ri, int ci):r(ri),c(ci){}
};
 
VVI imap;
VVI mov;
int dr[4] = {1,-1,0,0};
int dc[4] = {0,0,1,-1};
 
int main(){
    int n,m;
 
    scanf("%d%d",&n,&m);
    imap = VVI(m,VI(n,0));
    mov = VVI(m,VI(n,INF));
    for(int r = 0 ; r < m ; r++){
        char str[111];
        memset(str, 0x00, sizeof(str));
        scanf("%s",str);
        for(int c = 0 ; c < n ; c++){
            if(str[c]=='1') imap[r][c] = 1;
            else if(str[c]=='0') imap[r][c] = 0;
        }
    }
 
    queue<info> q;
    q.push(info(0,0));
    mov[0][0] = 0;
 
    while(!q.empty()){
        info here = q.front(); q.pop();
        for(int i = 0 ; i < 4 ; i++){
            int tr = here.r + dr[i];
            int tc = here.c + dc[i];
 
            if(0 <= tr && tr < m && 0 <= tc && tc < n){
                if(imap[tr][tc]==1){ // +1
                    if(mov[tr][tc] > mov[here.r][here.c] + 1){
                        mov[tr][tc] = mov[here.r][here.c] + 1;
                        q.push(info(tr,tc));
                    }
                }else if(imap[tr][tc]==0){
                    if(mov[tr][tc] > mov[here.r][here.c]){
                        mov[tr][tc] = mov[here.r][here.c];
                        q.push(info(tr,tc));
                    }
                }
            }
        }
    }
 
    printf("%d",mov[m-1][n-1]);
 
    return 0;
}