[ 백준 1261 ] 알고스팟 (c/c++)

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

 

 

[ 문제 요약 ]

상하좌우로 움직일 수 있고, 벽을 부술 수 있으며 미로의 크기를 나타내는 가로 M, 세로 N이 주어질 때, (N, M)으로 이동하려면 벽을 부수어야 하는 최소값을 출력한다.

 

 

[ 문제 풀이 ]

1. BFS을 이용하여 최단 경로를 구한다.

2. 만약 맵에서 1을 지나가게 된다면 벽을 부순 횟수를 1 더한다.

3. 현재 위치에서 이전에 벽을 부순 횟수와 이전 값을 비교하여 더 작은 수를 저장한다.

 

 

[ 소스 코드 ]

#include <bits/stdc++.h>
using namespace std;

int N, M;
int arr[111][111], D[111][111];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

void BFS(int a, int b) {
    queue<pair<int, int>> q;
    q.push(make_pair(a, b));

    while (!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        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 (arr[nx][ny] == 1){
                    if (D[nx][ny] > D[x][y] + 1){
                        D[nx][ny] = D[x][y] + 1;
                        q.push(make_pair(nx, ny));
                    }
                }
                else if (arr[nx][ny] == 0){
                    if (D[nx][ny] > D[x][y]){
                        D[nx][ny] = D[x][y];
                        q.push(make_pair(nx, ny));
                    }
                }
            } 
        }
    }
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    cin >> N >> M;
    for (int i=0; i<M; i++){
        string str; cin >> str;
        for (int j=0; j<N; j++){
            arr[i][j] = str[j] - '0';
            D[i][j] = 1e9;
        }
    }

    D[0][0] = 0;
    BFS(0, 0);
    cout << D[M-1][N-1];
    
    return 0;
}

 

 

 

[ 주의할 점 ]

BFS를 이용하되 pair를 이용하여 x, y 좌표를 구현하는 되는 문제이다.