[Silver / 21736] 헌내기는 친구가 필요해

문제 링크

---

🔷 분류

그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색, 격자 그래프

✒️ 문제 설명

2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 싶다.

도연이가 다니는 대학의 캠퍼스는 $N\times M$ 크기이며 캠퍼스에서 이동하는 방법은 벽이 아닌 상하좌우로 이동하는 것이다. 예를 들어, 도연이가 ($x$, $y$)에 있다면 이동할 수 있는 곳은 ($x+1$, $y$), ($x$, $y+1$), ($x-1$, $y$), ($x$, $y-1$)이다. 단, 캠퍼스의 밖으로 이동할 수는 없다.

불쌍한 도연이를 위하여 캠퍼스에서 도연이가 만날 수 있는 사람의 수를 출력하는 프로그램을 작성해보자.

⬅️ 입력

첫째 줄에는 캠퍼스의 크기를 나타내는 두 정수 $N$ ($1\le N\le 600$), $M$ ($1\le M\le 600$)이 주어진다.

둘째 줄부터 $N$개의 줄에는 캠퍼스의 정보들이 주어진다. O는 빈 공간, X는 벽, I는 도연이, P는 사람이다. I가 한 번만 주어짐이 보장된다.

➡️ 출력

첫째 줄에 도연이가 만날 수 있는 사람의 수를 출력한다. 단, 아무도 만나지 못한 경우 TT를 출력한다.

💻 코드 (C++)

#include <iostream>
#include <queue>
using namespace std;
char map[601][601];
bool visit[601][601];
queue<pair<int, int>> q;

int n, m;
int ans = 0;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

void BFS(int sx, int sy) {
	visit[sx][sy] = true;
	q.push({sx, sy});
	
	while(!q.empty()) {
		auto x = q.front().first;
		auto y = q.front().second;
		q.pop();
		for(int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			if(map[nx][ny] == 'X') continue;
			else if(map[nx][ny] == 'P' && !visit[nx][ny]) {
				visit[nx][ny] = true;
				ans++;
				q.push({nx, ny});
			} else if(map[nx][ny] == 'O' && !visit[nx][ny]) {
				visit[nx][ny] = true;
				q.push({nx, ny});
			}
		}
	}
}			

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int a, b;
	cin >> n >> m;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			char c;
			cin >> c;
			if(c == 'I') {
				a = i; b = j;
			}
			map[i][j] = c;
		}
	}
	BFS(a, b);
  if(ans == 0) cout << "TT";
	else cout << ans;
	return 0;
}