๋ณธ๋ฌธ์œผ๋กœ ๋ฐ”๋กœ๊ฐ€๊ธฐ
728x90
๐Ÿ”—๋ฌธ์ œ ๋ณด๋Ÿฌ๊ฐ€๊ธฐ
 

ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค

์ฝ”๋“œ ์ค‘์‹ฌ์˜ ๊ฐœ๋ฐœ์ž ์ฑ„์šฉ. ์Šคํƒ ๊ธฐ๋ฐ˜์˜ ํฌ์ง€์…˜ ๋งค์นญ. ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค์˜ ๊ฐœ๋ฐœ์ž ๋งž์ถคํ˜• ํ”„๋กœํ•„์„ ๋“ฑ๋กํ•˜๊ณ , ๋‚˜์™€ ๊ธฐ์ˆ  ๊ถํ•ฉ์ด ์ž˜ ๋งž๋Š” ๊ธฐ์—…๋“ค์„ ๋งค์นญ ๋ฐ›์œผ์„ธ์š”.

programmers.co.kr

 

๐Ÿ‘จ‍๐Ÿ’ปํ’€์ด ๊ณผ์ •

 

์ „ํ˜•์ ์ธ 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
๋ฐ˜์‘ํ˜•