백준 - 상남자(17267번)

 링크

우선순위 큐를 이용한 BFS로 풀이했다.

위 아래로 갈 수 있는 땅을 굳이 왼쪽, 오른쪽을 사용하여 갈 필요가 없다.

따라서 땅을 들를 때마다 그 땅의 위아래를 무조건 먼저 탐색한다.

위,아래 갈 때의 우선 순위를 1로 주고 왼쪽, 오른쪽 갈 때의 우선 순위를 0으로 주면 항상 위아래가 큐에서 먼저 나온다.

단, 큐에 왼쪽, 오른쪽밖에 남지 않았다면 이동 횟수가 적은 쪽에게 우선 순위를 높게 준다.

(이동 횟수 = 왼쪽, 오른쪽으로 간 횟수, 위아래는 이동 횟수에 포함시키지 않는다)

#include<iostream>
#include<memory.h>
#include<algorithm>
#include<math.h>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define FIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pii pair<int, int>
#define pdd pair<double, double>
#define pic pair<int, char>
#define ll long long
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<long long>
#define vc vector<char>
#define vii vector<pii>
#define IMAX 2000000001
#define LMAX 1000000000000000000
#define DMAX 0xFFFFFFFFFFFFF
#define MOD 100003
int mv1[4] = { 0, 0, 1, -1 };
int mv2[4] = { 1, -1, 0, 0 };
int mv_all1[8] = { 0, 1, 0, -1, -1, -1, 1, 1 };
int mv_all2[8] = { 1, 0, -1, 0 , -1, 1, -1, 1 };

int n, m;
int L, R;
int maps[1001][1001];
bool visit[1001][1001];
int prio[4];
priority_queue<pair<pii, pair<pii, pii>>> pq;

int main(void) {
	FIO;

	cin >> n >> m >> L >> R;

	int ans = 0;

	for (int i = 0; i < n; i++)
	{
		string str;
		cin >> str;
		for (int j = 0; j < m; j++)
		{
			maps[i][j] = int(str[j] - '0');
			if (maps[i][j] == 2) {
				pq.push({ {-1, 0}, {{i, j}, {0, 0}} });
			}
		}
	}

	prio[2] = 1;
	prio[3] = 1;
	//위아래 이동 시 우선 순위 높게

	while (!pq.empty()) {
		pii now = pq.top().second.first;
		pii LR = pq.top().second.second;
		int nowMove = -pq.top().first.second;
		pq.pop();

		if (LR.first > L || LR.second > R)	continue;
		if (visit[now.first][now.second])	continue;

		visit[now.first][now.second] = true;
		ans++;


		for (int i = 0; i < 4; i++)
		{
			int nx = now.first + mv1[i];
			int ny = now.second + mv2[i];

			if (nx < 0 || ny < 0 || nx >= n || ny >= m)	continue;
			if (maps[nx][ny] == 1)	continue;

			if (!visit[nx][ny]) {

				pii nextLR = LR;
				int nextMove = nowMove + 1;

				if (i == 0)
					nextLR.second++;
				else if (i == 1)
					nextLR.first++;
				else
					nextMove--;
				//위아래 이동 시 이동 횟수 0


				pq.push({ {prio[i], -nextMove }, {{nx, ny}, nextLR } });
				//이동 횟수가 적은 순으로 우선 순위 부여
			}
		}
	}

	cout << ans;
}