Coding Test] 게임 맵 최단거리 문제(BFS)

[Programmers School 문제 링크]

• Code

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

struct Pos
{
    int x; int y;
    Pos (int x, int y) : x(x), y(y){};
};
queue<Pos> q;

//Up, Left, Down, Right
int dx[4] = { 0, -1, 0, 1 };
int dy[4] = { -1, 0, 1, 0 };

int solution(vector<vector<int>> maps)
{
    int answer = -1;
    
    //Start Position
    maps[0][0] = 0;
    q.push(Pos(0, 0));
    
    //BFS
    int count = 1;
    while(!q.empty())
    {
        //Queue loop
        int loop = q.size();        
        for(int i = 0; i < loop; i++)
        {
            //Current position
            Pos cur = q.front();
            q.pop();
            
            //Goal
            if(cur.x == maps[0].size() - 1 && cur.y == maps.size() - 1)
                return count;
            
            //Check(Input Next)
            for(int idx_d = 0; idx_d < 4; idx_d++)
            {
                //Next Position (Up, Left, Down, Right)
                Pos n = Pos(cur.x + dx[idx_d], cur.y + dy[idx_d]);
                
                if(0 <= n.x && n.x < maps[0].size() &&  //Check X range
                   0 <= n.y && n.y < maps.size() &&     //Check Y range
                   maps[n.y][n.x] == 1)                 //Check Visit
                {
                    //Input
                    maps[n.y][n.x] = 0;
                    q.push(n);
                }
            }
        }
        //Count;
        count++;
    }    
    return answer;
}

---

• 반복문으로 방향 검사를 하기 위해 int[4] 선언

//Pos(dx[0], dy[0]) = Up
//Pos(dx[1], dy[1]) = Left
//Pos(dx[2], dy[2]) = Down
//Pos(dx[3], dy[3]) = Right
int dx[4] = { 0, -1, 0, 1 };
int dy[4] = { -1, 0, 1, 0 };

• BFS 탐색 부분

//첫 칸부터 카운팅
int count = 1;
//BFS 시작
while(!q.empty())
{
    //Loop 중 큐에 새로 추가되는 요소는 배제하기 위해 Size 저장
    int loop = q.size();
    for(int i = 0; i < loop; i++)
    {
        //큐에서 위치 꺼내오기
        Pos cur = q.front();
        q.pop();

        //이번 위치가 도착 지점이라면 count를 반환(종료)
        if(cur.x == maps[0].size() - 1 && cur.y == maps.size() - 1)
            return count;

        //이번 위치에서 이동할 수 있는 위치 탐색
        for(int idx_d = 0; idx_d < 4; idx_d++)
        {
            //다음 위치(Up, Left, Down, Right)
            Pos n = Pos(cur.x + dx[idx_d], cur.y + dy[idx_d]);

            if(0 <= n.x && n.x < maps[0].size() &&  //0 <= x < max
               0 <= n.y && n.y < maps.size() &&     //0 <= y < max
               maps[n.y][n.x] == 1)                 //미방문 검사
            {
                maps[n.y][n.x] = 0;    //방문 체크
                q.push(n);             //큐에 추가
            }
        }
    }
    //이동한 횟수 증가
    count++;
}