[프로그래머스] Level 2 : 무인도 여행

https://school.programmers.co.kr/learn/courses/30/lessons/154540

프로그래머스

 

일반적인 상하좌우 BFS로 풀었다.

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

int dy[]{ -1, 0, 1, 0 };
int dx[]{ 0, 1, 0, -1 };

vector<int> solution(vector<string> maps) {
	vector<int> answer;
	vector<vector<bool>> Visit(maps.size(), vector<bool>(maps[0].size(), false));

	for (int y = 0; y < maps.size(); ++y)
	{
		for (int x = 0; x < maps[0].size(); ++x)
		{
			if (maps[y][x] == 'X' || Visit[y][x]) continue;
			int Food = 0;
			Food += maps[y][x] - '0';

			queue<pair<int, int>> q;
			q.push({ y, x });
			Visit[y][x] = true;

			while (!q.empty())
			{
				int cy = q.front().first, cx = q.front().second;
				q.pop();

				for (int i = 0; i < 4; ++i)
				{
					int ny = cy + dy[i], nx = cx + dx[i];
					if (ny < 0 || nx < 0 || ny >= maps.size() || nx >= maps[0].size() || Visit[ny][nx] || maps[ny][nx] == 'X') continue;

					Food += maps[ny][nx] - '0';
					Visit[ny][nx] = true;
					q.push({ ny, nx });
				}
			}
			if (Food > 0) answer.push_back(Food);
		}
	}

	if (answer.empty()) return { -1 };
	sort(answer.begin(), answer.end());
	return answer;
}