[백준 C++] 21736 : 헌내기는 친구가 필요해

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

DFS BFS다 가능한 문제이다.

입력으로 주어진 맵에 따라서 돌아다니며 방문할 수 있는 위치에 있는 P의 갯수를 찾으면 된다.

전형적인 탐색 문제이므로 아는 방식 그대로 적용해서 풀면 된다.

---

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int dx[] = { 1, 0, -1, 0 };
int dy[] = { 0, 1, 0, -1 };
vector<vector<char>> campus;
int N, M;

void calculate(int startY, int startX) 
{
	int ans = 0;

	queue<pair<int, int>> que;

	que.push(make_pair(startY, startX));
	campus[startY].at(startX) = 'X';

	while (!que.empty())
	{
		int currentY = que.front().first;
		int currentX = que.front().second;
		que.pop();

		for (int i = 0; i < 4; i++)
		{
			int nextY = currentY + dy[i];
			int nextX = currentX + dx[i];

			if (nextY >= 0 && nextY < N && nextX >= 0 && nextX < M)
			{
				char nextValue = campus[nextY].at(nextX);
				
				switch (nextValue)
				{
				case 'O':
					que.push(make_pair(nextY, nextX));
					campus[nextY].at(nextX) = 'X';
					break;
				case 'P':
					que.push(make_pair(nextY, nextX));
					campus[nextY].at(nextX) = 'X';
					ans += 1;
					break;
				default:
					break;
				}
			}
		}
	}

	if (ans == 0)
		cout << "TT\n";
	else
		cout << ans << '\n';
}

int main()
{
	int startX, startY;
	cin >> N >> M;

	campus = vector<vector<char>>(N, vector<char>(M, 'O'));

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			char temp;
			cin >> temp;
			campus[i].at(j) = temp;

			if (temp == 'I')
			{
				startX = j;
				startY = i;
			}
		}
	}

	calculate(startY, startX);

	return 0;
}

bfs로 풀었는데, 맵과 시작하는 도연이의 위치를 caculate함수로 전달해준다.

4개의 방향으로 이동해가면서 이동한 지점을 'X'로 수정해주고 (visited를 사용하지 않기 위해서) P를 만날 때마다 ans를 더해주었다.