[백준] 알고스팟

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

1261번: 알고스팟

우선 문제부터 요약하면, 

 

미로에 사람들이 갇혀있는데, 미로의 어떤 부분은 빈 방이 아니라 벽이라고 합니다. 벽을 부시는 횟수를 최소화 해서 가장 왼쪽 상단에서 가장 오른쪽 하단으로 이동하려 할 때, 최소로 벽을 부시는 횟수를 구해야 하는 문제입니다.

 

<Soltuion>

많이 나오는 미로 찾기 문제 유형입니다. 

 

bfs를 이용하였고, bfs의 상태가 발전하는경우 (즉 queue에 넣는 경우)는 해당 방에 도달할 때 부신 벽의 수가 더 적을 때만 발전하게 하여, 문제를 해결하였습니다. 

 

실제 구현은 아래와 같습니다. 

#include <iostream>
#include <queue>

char grid[100+20][100+20];
int cost_grid[100+20][100+20];

int M, N;

int dir_lookup_r[] = {-1, 1, 0, 0};
int dir_lookup_c[] = {0, 0, -1, 1};

using namespace std;

struct rc_and_cost{
    int r;
    int c;
    int cost;
};

void getinput(){
    cin >> M >> N;
    for(int i = 1; i <= N; i++){
        cin >> &grid[i][1];
    }    
}

int solution(){
    // initialize cost_grid
    for(int i = 1; i<=N; i++){
        for(int j = 1; j<=M; j++){
            if(i==1 && j==1) continue;
            cost_grid[i][j] = 987654321;
        }
    }

    // bfs
    queue <rc_and_cost> q;
    q.push(rc_and_cost{1,1,0});

    while(!q.empty()){
        struct rc_and_cost cur = q.front(); q.pop();
        // DEBUG
        // cout << cur.r << ' ' << cur.c << ' ' << cur.cost <<endl;
        //check 4 positions
        for(int i = 0; i<4; i++){
            int new_r = cur.r+dir_lookup_r[i];
            int new_c = cur.c+dir_lookup_c[i];

            // check if new_r, new_c not oob
            if(!(0<new_r && new_r <=N && 0<new_c && new_c <= M)) continue;

            int new_cost = cur.cost + (grid[new_r][new_c]-'0');

            if(cost_grid[new_r][new_c]<= new_cost) continue;

            // 갱신
            cost_grid[new_r][new_c] = new_cost;
            // 마지막 지점이 아니라면 상태발전
            if(new_r == N && new_c == M) continue;
            q.push(rc_and_cost{new_r,new_c,new_cost});
        }

    }
    return cost_grid[N][M];
}

int main(){
    getinput();

    // solve
    cout << solution() << endl;;

}