백준 2917번 늑대 사냥꾼

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

조건이 많이 붙어있는 BFS(Breadth First Search) 알고리즘 문제였습니다.

해당 문제를 풀기 위해서는 나무들로부터의 최소거리를 찾기 위해 queue 자료구조를 사용해야하고 경로를 찾기 위해서는 priority_queue를 사용해야합니다.

나무들로부터의 최소거리를 찾는 것까지는 성공했으나 경로를 priority_queue를 이용해서 풀 생각을 못 했기 때문에 kdk8361님(http://organize-study.tistory.com/34) 포스팅을 참고해서 풀었습니다.

알고리즘은 아래와 같습니다.

1. dist[][] 배열은 나무들로부터의 최소거리이기 때문에 나무들의 좌표를 queue에 넣고 dist[i][j] = 0으로 초기화합니다. 나머지 칸들은 dist[i][j] = -1로 초기화합니다.

2. 우선 큐에 있는 나무들로부터의 최소거리를 계산합니다.

3. 늑대는 나무들로부터 최대한 멀리 떨어진 칸을 통해 오두막으로 이동하므로 최대 우선순위 큐 즉, maxHeap을 이용합니다.

i) 인자는 총 4개인데 다음과 같습니다: {현재 칸에서 나무들로부터의 최대 거리 중 최소, 여태까지 경로 중 나무들로부터의 최대 거리 중 최소, {현재 좌표}}

ii) queue를 이용한 BFS가 아니라 우선순위 큐를 이용한 BFS이므로 큐에 넣을 때마다 방문 표시를 해서는 메모리 초과를 방지하지 못합니다.

iii) 따라서 dist[현재 좌표 y][현재 좌표 x]가 -1인지 확인하고(-1이 방문했다는 표시) -1이라면 continue를 하도록 합니다.

iv) 아직 방문하지 않은 칸이라면 기존 BFS처럼 4가지 방향에 대해 우선순위 큐에 넣어줍니다.

4. 오두막에 도착하면 여태까지 경로 중 최소 거리를 출력하고 마칩니다.

#include <iostream>

#include <vector>

#include <string>

#include <queue>

#include <algorithm>

#include <cstring>

using namespace std;

 

const int MAX = 500;

const int INF = 987654321;

 

typedef struct

{

        int y, x;

}Dir;

 

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

 

int N, M;

pair<int, int> start, destination;

string graph[MAX];

int dist[MAX][MAX];

queue<pair<int, int>> tree;

//현재 칸의 나무로부터 최소 거리, 여태까지의 나무로부터 최소 거리, 칸

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

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> N >> M;

 

        memset(dist, -1, sizeof(dist));

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

        {

                 cin >> graph[i];

                 for (int j = 0; j < M; j++)

                         if (graph[i][j] == '+')

                         {

                                 dist[i][j] = 0;

                                 tree.push({ i, j });

                         }

                         else if (graph[i][j] == 'V')

                                 start = { i, j };

                         else if (graph[i][j] == 'J')

                                 destination = { i, j };

        }

 

        //나무들로부터 최소거리 계산

        while (!tree.empty())

        {

                 int y = tree.front().first;

                 int x = tree.front().second;

                 tree.pop();

 

                 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 && dist[nextY][nextX] == -1)

                         {

                                 dist[nextY][nextX] = dist[y][x] + 1;

                                 tree.push({ nextY, nextX });

                         }

                 }

        }

 

        //현재 칸의 나무들로부터 최소 거리, 여태까지의 나무들로부터 최소 거리, 칸

        pq.push({ dist[start.first][start.second], {dist[start.first][start.second], {start.first, start.second} } });

        while (!pq.empty())

        {

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

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

                 int distance = pq.top().first;

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

                 pq.pop();

 

                 if (curY == destination.first && curX == destination.second)

                 {

                         cout << minDistance << "\n";

                         break;

                 }

                 //queue를 이용한 BFS가 아닌

                 //priority queue를 이용한 BFS이므로 이 부분이 핵심

                 if (dist[curY][curX] == -1)

                         continue;

 

                 //방문했다고 표시

                 dist[curY][curX] = -1;

 

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

                 {

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

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

 

                         //이미 도달한 칸이 아닌 경우에만

                         if (0 <= nextY && nextY < N && 0 <= nextX && nextX < M && dist[nextY][nextX] != -1)

                                 pq.push({ dist[nextY][nextX], {min(dist[nextY][nextX], minDistance), {nextY, nextX}} });

                 }

        }

        return 0;

}

개발환경:Visual Studio 2017

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