[BFS] 백준 1261번 알고스팟(C++)

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

 

처음에 진짜 문제부터 이해 못할뻔했다.

 

뭔 알고스팟에 있다면....

뭔 궁극의 무기 sudo....

 

그냥 문제는 n*n 크기의 방들이 주어지고

0은 지날 수 있는곳

1은 벽

이다.

 

그리고 1,1 위치부터 n,n 까지의 위치까지 가기 위해서 최소 몇개의 벽을 부숴야 하는가?
에 대한 문제인것

 

문제 풀이에 앞서

[BFS] 백준 13549번 숨바꼭질 3(C++)

[BFS] 백준 13549번 숨바꼭질 3(C++)

숨바꼭질 3번과 비슷하다는 느낌을 받았다.

 

숨바꼭질 3번 문제가 뭐였는가?

한 선형 위치에 따른 시간 위치의 변화를 사용한 해당 위치로 가기위한 최소의 비용 구하기

 

였는데

 

이번 문제는 선형 위치가 아닌 2차원 의 위치에 있는 것이고,

특정 행동에 대한 비용이 늘어나거나 늘어나지않음.

 

이 공통적이다.

 

우리는 나아갈 수 있는 면이 모두 1(벽)으로 둘러쌓였을때, 1을 뿌시면 비용이 1증가한다는 전제조건이 존재한다.

 

숨바꼭질3번을 풀었을때 내가 애먹었던 부분은

 

"q안에 같은 위치로 가지만 더 작은 비용이 존재한다. 하지만 순서상 더 큰 비용이 먼저 pop 되기 때문에 더 작은 비용이 오기전에 프로그램이 종료된다"

 

였다.

 

그렇다면? 이 벽 뿌수기 문제또한 동일한 것이다.

 

예를들어

 

010

111

100

 

이란 미로가 있다고 해보자

여기서 1,1 에서 출발해서 

먼저 ㄱ 모양으로 가는 경우를 생각해보자

 

3,3 까지 1을 세번 뿌시니 3,3 q에는 비용이 3이 들어가고

3,3까지 벽을 두번 뿌시니 비용이 2가 들어간다

 

하지만 만약 우리가 순서상 

bfs를 사용한다고 했을때

 

이렇게 왼쪽에 있는 벽부터 고려를 한다고 하면, 3,3 의 q안에는 비용이 3이 먼저 들어가고 2가 들어간다

 

그럼 해당 위치의 q가 pop될때, 조건문을 통해 프로그램이 종료하게 되는 문제가 발생한다

 

그렇다면?

 

숨바꼭질 3에서 해줬던 것 처럼 우선순위 큐를 사용한다

 

#include <iostream>

#include <queue>

#include <vector>

#include <tuple>

using namespace std;

void bfs();

int visited[102][102];

int dx[4] = {0, 0, 1, -1};

int dy[4] = {1, -1, 0, 0};

int n, m, arr[102][102];

struct obj

{

    int t, x, y;

    bool operator>(const obj &other) const

    {

        return t > other.t;

    }

};

int main()

{

    cin >> n >> m;

    for (int i = 1; i <= m; i++)

    {

        string s;

        cin >> s;

        for (int j = 1; j <= n; j++)

        {

            arr[i][j] = s[j - 1] - '0';

        }

    }

    bfs();

}

void bfs()

{

    priority_queue<obj, vector<obj>, greater<>> q;

    q.push(obj{0, 1, 1});

    for (int i = 1; i <= m; i++)

    {

        for (int j = 1; j <= n; j++)

        {

            visited[i][j] = 99999999;

        }

    }

    while (!q.empty())

    {

        int x = q.top().x;

        int y = q.top().y;

        int t = q.top().t;

        q.pop();

        if (t > visited[y][x])

            continue;

        if (x == n && y == m)

        {

            cout << t << "\n";

            return;

        }

        for (int i = 0; i < 4; i++)

        {

            int nx = x + dx[i];

            int ny = y + dy[i];

            if (nx >= 1 && ny >= 1 && nx <= n && ny <= m)

            {

                int cost = t + (arr[ny][nx] == 1 ? 1 : 0);

                if (cost < visited[ny][nx])

                {

                    visited[ny][nx] = cost;

                    q.push({cost, nx, ny});

                }

            }

        }

    }

}

 

시간 x,y위치를 고려하기 위해 obj라는 구조체를 만들었으며

우선순위 큐에서는 greater라는 것을 통해 정렬을 해 주는데 이때 operator > 가 필요하다.

그래서 안에 operator문을 일부러 설정해 주었다

 

또한 들어가려는 좌표의 비용이 다른 좌표의 의한 비용보다 크다면, skip을 하도록 하였다.