[백준] 1261 - 알고스팟

BFS에 올리긴 했지만, 다익스트라 문제

벽 부수고 이동하기와 같은 문제인 듯 하지만, 이동거리가 최소가 아닌, 벽을 최소로 부수는 것

1. visit배열을 선언해서 최대값으로 초기화

2. BFS탐색을 하면서 벽이 있는 것을 dis로 계산해서 이동위치가 최소가 되는 지점만 큐에 담는다

3. 도착위치에 있는 visit을 출력

#include <iostream>
#define MX 102
using namespace std;
 
struct ALGO {
    int x, y;
}q[MX*MX*MX];
 
int map[MX][MX], visit[MX][MX];
int dx[] = { 0, 0, -1, 1 };
int dy[] = { -1, 1, 0, 0 };
int N, M, dab = 987654321;
 
int bfs()
{
    int st, ed, ix, iy, in, nx, ny;
    for (int i = 0; i < M; i++)
        for (int j = 0; j < N; j++)
            visit[i][j] = 987654321;
    st = ed = -1;
    q[++st].x = 0; q[st].y = 0; visit[0][0] = 0;
    while (st != ed)
    {
        ix = q[++ed].x; iy = q[ed].y;
        for (int i = 0; i < 4; i++)
        {
            nx = ix + dx[i]; ny = iy + dy[i];
            if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
            int dis = visit[iy][ix] + map[ny][nx];
            if (dis < visit[ny][nx]) {
                q[++st].x = nx; q[st].y = ny; visit[ny][nx] = dis;
            }
        }
    }
    return visit[M - 1][N - 1];
}
 
int main(void)
{
    cin >> N >> M;
    for(int i = 0; i<M; i++)
        for (int j = 0; j < N; j++)
        {
            char c;
            cin >> c;
            map[i][j] = c - '0';
        }
    cout << bfs() << endl;
    return 0;
}