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

코드

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

const int dx[] = { 1,-1,0,0 };
const int dy[] = { 0,0,1,-1 };
int n, m, visited[603][603],res;
char a[603][603];
string s;
pair<int, int> doyeon;
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> s;
		for (int j = 0; j < m; j++) {
			a[i][j] = s[j];
            // 도연이 위치 저장
			if (a[i][j] == 'I') {
				doyeon.first = i;
				doyeon.second = j;
			}
		}
	}
	queue<pair<int, int>> q;
	visited[doyeon.first][doyeon.second] = 1;
	q.push(make_pair(doyeon.first, doyeon.second));
	while (!q.empty()) {
		int px = q.front().first;
		int py = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = px + dx[i];
			int ny = py + dy[i];
            // 범위를 벗어나거나, 벽이거나, 이미 방문했다면 다른 방향 탐색
			if (nx >= n || ny >= m || nx < 0 || ny < 0 || visited[nx][ny] || a[nx][ny] == 'X') continue;
			if (a[nx][ny] == 'P') res++;
			visited[nx][ny] = 1;
			q.push(make_pair(nx, ny));
		}
	}
	if (res == 0) {
		cout << "TT\n";
		return 0;
	}
	cout << res << '\n';
	return 0;
}

풀이

그래프 탐색 문제였다. 도연이의 위치를 저장해두고, 그래프 탐색을 통해 만날 수 있는 사람을 구해주면 되는 문제. bfs를 써도 되고 dfs를 써도 되는 문제이다.