[백준/BOJ] 백준 17267번 : 상남자

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

17267번: 상남자

BFS를 통해 갈 수 있는 땅의 개수를 확인하는데, 탐색할 위치를 확인할 때, 이전에 확인할 때 보다 왼쪽으로 움직일 수 있는 횟수 또는 오른쪽으로 움직일 수 있는 횟수가 큰 경우일 때만 큐에 넣어서 탐색을 진행하도록 하여 문제를 해결했다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;

int n, m;
int l, r;
vector<string> board;
pair<int, int> start;
pair<int, int> discovered[1005][1005]; //[행][열] = (왼쪽으로 움직일 수 있는 최댓값, 오른쪽으로 움직일 수 있는 최댓값)
queue<pair<pair<int, int>, pair<int, int>>> q; //((위치),(왼쪽으로 움직일 수 있는 값, 오른쪽으로 움직일 수 있는 값))
int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };

void Pre() {

	for (int i = 0; i < 1005; i++) {
		for (int j = 0; j < 1005; j++) {
			discovered[i][j] = make_pair(-1, -1);
		}
	}
}

void Bfs() {

	discovered[start.first][start.second] = make_pair(l, r);
	q.push(make_pair(start, make_pair(l, r)));

	while (!q.empty()) {
		pair<int, int> here = q.front().first;
		pair<int, int> here_can_move = q.front().second;
		q.pop();

		for (int dir = 0; dir < 4; dir++) {
			pair<int, int> there = make_pair(here.first + dxdy[dir][0], here.second + dxdy[dir][1]);
			pair<int, int> there_can_move = here_can_move;

			//범위에 벗어나거나, 장애물이 있을때
			if (there.first < 0 || there.first >= n || there.second < 0 || there.second >= m || board[there.first][there.second] == '1') {
				continue;
			}

			if (dir == 1 || dir == 3) { //위로 또는 아래로 움직일때

				if (discovered[there.first][there.second].first < here_can_move.first && discovered[there.first][there.second].second < here_can_move.second) {
					discovered[there.first][there.second].first = here_can_move.first;
					discovered[there.first][there.second].second = here_can_move.second;
					q.push(make_pair(there, here_can_move));
				}

				else if (discovered[there.first][there.second].first < here_can_move.first) {
					discovered[there.first][there.second].first = here_can_move.first;
					q.push(make_pair(there, here_can_move));
				}

				else if (discovered[there.first][there.second].second < here_can_move.second) {
					discovered[there.first][there.second].second = here_can_move.second;
					q.push(make_pair(there, here_can_move));
				}

			}

			else { //왼쪽 또는 오른쪽으로 움직일때

				//왼쪽으로 움직일 수 없을때
				if (dir == 0 && here_can_move.first <= 0) {
					continue;
				}

				//오른쪽으로 움직일 수 없을때
				if (dir == 2 && here_can_move.second <= 0) {
					continue;
				}

				//왼쪽 방향
				if (dir == 0) {
					there_can_move.first--;
				}

				//오른쪽 방향
				else {
					there_can_move.second--;
				}

				if (discovered[there.first][there.second].first < there_can_move.first) {
					discovered[there.first][there.second].first = there_can_move.first;
					q.push(make_pair(there, there_can_move));
				}

				if (discovered[there.first][there.second].second < there_can_move.second) {
					discovered[there.first][there.second].second = there_can_move.second;
					q.push(make_pair(there, there_can_move));
				}

			}
		}


	}

}

int Solve()
{
	int ret = 0;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (discovered[i][j].first != -1)
				ret++;
		}
	}

	return ret;
}

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

	Pre();

	cin >> n >> m;
	cin >> l >> r;

	for (int i = 0; i < n; i++) {
		string input;
		cin >> input;

		board.push_back(input);

		for (int j = 0; j < input.size(); j++) {
			if (input[j] == '2') {
				start = make_pair(i, j);
			}
		}
	}

	Bfs();
	cout << Solve();

	return 0;
}