[Silver 2] 21736번 현내기는 친구가 필요해

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

21736번: 헌내기는 친구가 필요해

 

이 문제는 BFS를 통해 길찾기를 하면 해결할 수 있다.

길찾기를 진행하다 P를 만나면 counter를 증가시킨다.

모든 탐색이 끝나고 counter가 초기 상태와 같다면 TT를 출력한다.

 

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

char graph[601][601];
int visited[601][601] = { 0, };
int N, M, counter = 0;
int dx[] = { 0,0,1,-1 };
int dy[] = { -1,1,0,0 };
queue<pair<int, int>> q;

void bfs(int x,int y) {
	q.push(make_pair(y, x));
	visited[y][x] = 1;
	while (!q.empty()) {
		int ny = q.front().first;
		int nx = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int uy = ny + dy[i];
			int ux = nx + dx[i];

			if (uy < 0 || ux < 0 || uy>=N || ux>=M) continue;
			if (graph[uy][ux] == 'X') continue;

			if (!visited[uy][ux]) {
				q.push(make_pair(uy, ux));
				visited[uy][ux] = 1;
				if (graph[uy][ux] == 'P') counter += 1;
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N >> M;
	int x = 0, y = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			char value;
			cin >> value;
			graph[i][j] = value;
			if (value == 'I') {
				x = j;
				y = i;
			}
		}
	}
	bfs(x, y);
	if (counter == 0) cout << "TT" << '\n';
	else cout<<counter<<'\n';
}