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

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

문제

입력

 

 

 

출력

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

 

 

풀이과정

"I라는 값이 상하좌우로만 움직일 수 있을때 만날 수 있는 P의 개수는 몇개인가?"라는 문제였고,

해당문제는 말 그대로 상화좌우를 모두 탐색하여 P의 개수를 구한다음 출력하면 되기때문에 BFS 알고리즘을 하여 모든 구간을 다 도는 방식으로 코드를 구상하였습니다.

 

code

#include <iostream>
#include <queue>

char campus[601][601];
char checkMap[601][601];

int		bfs(int n, int m, int placeY, int placeX)
{
	int count = 0;
	std::queue <std::pair<int, int> > que;
	std::pair <int, int> Doyeon;

	que.push(std::make_pair(placeY, placeX));
	while (!que.empty())
	{
		Doyeon = que.front();
		que.pop();
		if (!checkMap[Doyeon.first][Doyeon.second]) {
			// std::cout << campus[Doyeon.first][Doyeon.second] << "\n";
			if (campus[Doyeon.first][Doyeon.second] == 'P')
				count++;
			if (Doyeon.first + 1 < n && !checkMap[Doyeon.first + 1][Doyeon.second]) {
				if (campus[Doyeon.first + 1][Doyeon.second] != 'X')
					que.push(std::make_pair(Doyeon.first + 1, Doyeon.second));
			}
			if (0 <= Doyeon.first - 1 && !checkMap[Doyeon.first - 1][Doyeon.second]) {
				if (campus[Doyeon.first - 1][Doyeon.second] != 'X')
					que.push(std::make_pair(Doyeon.first - 1, Doyeon.second));
			}
			if (Doyeon.second + 1 < m && !checkMap[Doyeon.first][Doyeon.second + 1]) {
				if (campus[Doyeon.first][Doyeon.second + 1] != 'X')
					que.push(std::make_pair(Doyeon.first, Doyeon.second + 1));
			}
			if (0 <= Doyeon.second - 1 && !checkMap[Doyeon.first][Doyeon.second - 1]) {
				if (campus[Doyeon.first][Doyeon.second - 1] != 'X')
					que.push(std::make_pair(Doyeon.first, Doyeon.second - 1));
			}
			checkMap[Doyeon.first][Doyeon.second] = 1;
		}
	}
	return count;
}

int		main(void)
{
	int n, m;
	int	placeX, placeY, count;

	std::cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			std::cin >> campus[i][j];
			if (campus[i][j] == 'I') {
				placeY = i;
				placeX = j;
			}

		}
	}
	count = bfs(n, m, placeY, placeX);
	if (count == 0) std::cout << "TT" << "\n";
	else std::cout << count << "\n";

	return (0);
}

 

후기

익숙했던 유형의 문제가 크게 어렵지않게 접근할 수 있었던 거 같다.

탐색하는 과정에서 똑같은 코드가 4번 반복이 되어 탐색하는 방법을 배열로 담으면 훨씬 깔끔하게 코드를 구상할 수 있을 거 같다.