728x90
๐๋ฌธ์ ๋ณด๋ฌ๊ฐ๊ธฐ
๐จ๐ปํ์ด ๊ณผ์
์ ํ์ ์ธ BFS ๋ฌธ์ ์ธ ๊ฒ ๊ฐ์ต๋๋ค. ์ ํ์ฌํญ๋ค๋ ๋น๊ต์ ์ฌ์ด ํธ์ด๋ผ ์ด๋ ต์ง ์๊ฒ ๊ตฌํํ ์ ์์์ต๋๋ค.
โ๏ธ์์ค ์ฝ๋ ๋ฐ ๊ฒฐ๊ณผ
#include <vector>
#include <queue>
using namespace std;
using Position = pair<int, int>;
using Matrix = vector<vector<int>>;
vector<Position> directions { {-1, 0}, { 1, 0 }, { 0, -1 }, { 0, 1 } }; // ์, ํ, ์ข, ์ฐ
int FindEnemyCampWithMinCount(Matrix& maps, Position player, const Position enemyCamp) // BFS
{
int maxRow = maps.size(), maxCol = maps[0].size();
queue<Position> _queue;
_queue.emplace(player);
maps[player.first][player.second] = 2; // 1๋ก ์์ํ๋ ค๊ณ ํ์ผ๋, 1์ด ๊ฐ ์ ์๋ ๊ณณ์ผ๋ก ๊ฐ์ฃผ ๋์ด์
// ๋ค ํฉํ ๊ฐ์์ -1 ํ๊ฒ ์ต๋๋ค.
while(!_queue.empty())
{
Position current = _queue.front();
_queue.pop();
for (int i = 0; i < directions.size(); i++)
{
int nextRow = current.first + directions[i].first;
int nextCol = current.second + directions[i].second;
if (nextRow < 0 or nextRow >= maxRow or nextCol < 0 or nextCol >= maxCol)
continue;
if (maps[nextRow][nextCol] == 0 or maps[nextRow][nextCol] > 1)
continue;
maps[nextRow][nextCol] = maps[current.first][current.second] + 1;
_queue.emplace(nextRow, nextCol);
}
}
return maps[enemyCamp.first][enemyCamp.second] == 1 ? -1 : maps[enemyCamp.first][enemyCamp.second] - 1;
}
int solution(vector<vector<int>> maps)
{
Position player(0, 0);
Position enemyCamp(maps.size() - 1, maps[0].size() - 1);
return FindEnemyCampWithMinCount(maps, player, enemyCamp);
}
728x90
๋ฐ์ํ
'๐คAlgorithm > Programmers' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Programmers] Lv2. [3์ฐจ] ํ์ผ๋ช ์ ๋ ฌ | C++ (0) | 2023.06.24 |
---|---|
[Programmers] Lv2. ๋ฐฉ๋ฌธ ๊ธธ์ด | C++ (0) | 2023.06.24 |
[Programmers] Lv2. ์ฃผ์๊ฐ๊ฒฉ | C++ (0) | 2023.06.22 |
[Programmers] Lv2. ๋ ๋ฐ๋จน๊ธฐ | C++ (0) | 2023.06.22 |
[Programmers] Lv2. ์คํ์ฑํ ๋ฐฉ | C++ (0) | 2023.06.21 |