백준 1261번 알고스팟

문제 링크입니다: https://www.acmicpc.net/problem/1261

우선순위 큐를 이용한 BFS(Breadth First Search) 알고리즘을 통해 푼 문제였습니다.

백준 13549번 숨바꼭질 3(http://jaimemin.tistory.com/583)과 유사한 문제였습니다.

깨드린 블럭을 기준으로 우선순위 큐를 선언하여 BFS 알고리즘을 적용하면 쉽게 풀 수 있는 문제였습니다.

*다익스트라 알고리즘을 통해서도 풀 수 있다고 합니다.

#include <iostream>

#include <string>

#include <vector>

#include <queue>

#include <functional>

#include <algorithm>

using namespace std;

 

const int MAX = 100;

 

typedef struct

{

        int y, x;

}Dir;

 

Dir moveDir[4] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };

 

int M, N;

string input[MAX];

bool visited[MAX][MAX];

 

int BFS(void)

{

        //깨드린 블록을 기준으로 최소 힙 선언

        priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;

        pq.push({ 0, {0, 0} });

        visited[0][0] = true;

 

        while (!pq.empty())

        {

                 int y = pq.top().second.first;

                 int x = pq.top().second.second;

                 int block = pq.top().first;

                 pq.pop();

 

                 if (y == N - 1 && x == M - 1)

                         return block;

 

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

                 {

                         int nextY = y + moveDir[i].y;

                         int nextX = x + moveDir[i].x;

 

                         if (0 <= nextY && nextY < N && 0 <= nextX && nextX < M)

                         {

                                 if (!visited[nextY][nextX])

                                 {

                                          if (input[nextY][nextX] == '1')

                                                  pq.push({ block + 1,{ nextY, nextX } });

                                          else

                                                  pq.push({ block, {nextY, nextX} });

                                          visited[nextY][nextX] = true;

                                 }

                         }

                 }

        }

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> M >> N;

 

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

                 cin >> input[i];

 

        cout << BFS() << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~