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

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

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

---

알고리즘 분류

 

그래프 탐색(BFS, DFS)

 

---

해설

 

#include <iostream>
#include <queue>
using namespace std;
int main() {
	int N, M, ix, iy;
	cin >> N >> M;
	char** campus = new char* [N];
	bool** visit = new bool* [N];
	for (int i = 0; i < N; i++) {
		campus[i] = new char[M];
		visit[i] = new bool[M];
		for (int j = 0; j < M; j++) {
			cin >> campus[i][j];
			visit[i][j] = 0;
			if (campus[i][j] == 'I') {
				ix = i; iy = j; // I의 좌표 저장
			}
		}
	}

	int people = 0; // 만난 사람의 수
	int dx[4] = { 1,-1,0,0 };
	int dy[4] = { 0,0,1,-1 };

	queue<pair<int, int>> q;
	q.push(make_pair(ix, iy));
	while (!q.empty()) { // BFS 알고리즘
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nx = dx[i] + x;
			int ny = dy[i] + y;
			if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
				if (visit[nx][ny] == 0) {
					if (campus[nx][ny] != 'X') {
						q.push(make_pair(nx, ny));
						if (campus[nx][ny] == 'P')
							people++;
					}
					visit[nx][ny] = 1;
				}
			}
		}
	}
	if (people == 0) cout << "TT";
	else cout << people;
}

전형적인 BFS 알고리즘 문제입니다

 

실버2라는 난이도로 그래프 이론 문제 중 낮은 편으로

BFS 알고리즘 입문자들이 공부하기 좋은 문제

 

visit 배열과 campus 배열(그래프)을 동적할당 하고

방문하지 않은 곳들을 상하좌우로 방문하며

P를 찾아내는 방식입니다.

 

아래는 유사한 방식의 BFS 알고리즘을 활용한 문제들입니다

 

[14940번] 쉬운 최단거리

 

[7562번] 나이트의 이동