[프로그래머스/c++] 게임 맵 최단거리

문제 접근

• 캐릭터가 적 팀의 진영까지 가는 가장 빠른 길을 찾는 것으로, 최단 경로를 찾는 문제이다.
• 최단 경로를 찾는 문제의 경우 제일 먼저 BFS가 떠오른다!
  • DFS의 경우 재귀함수를 호출하여 스택을 사용하므로 구조상 모든 경로를 다 탐색해보아야 하므로 BFS에 비해 시간이 오래 걸린다.

BFS를 이용하여 최단거리를 구한다!

 

---

성공 코드

• 각각의 위치를 구조체 Loc를 통해 구현한다.
• 큐에 시작 위치인 (0, 0)을 넣는다.
• 큐가 비어있지 않은 동안 다음을 반복한다.
  • 큐에 들어있는 원소를 하나 pop하여 pop한 원소의 위치에서 상, 하, 좌, 우를 탐색하며 게임 맵 크기의 범위에 들어가고 방문하지 않은 위치라면
    • 큐에 해당 위치를 넣는다.
    • 해당 위치의 distance를 pop한 원소의 위치까지의 distance에 +1한 값으로 변경한다.
• 상대 팀 진영의 distance가 0이라면 도착할 수 없다는 것을 의미하므로 -1을 리턴하고  0보다 큰 경우 해당 distance를 리턴한다.

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

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

struct Loc{
    int x, y;
    Loc(int x, int y){
        this->x=x;
        this->y=y;
    }
};

queue<Loc> q;

int solution(vector<vector<int> > maps)
{
    int answer = 0;
    int row_size=maps.size();
    int column_size=maps[0].size();
    vector<vector<int> > distance(row_size, vector<int> (column_size, 0));
    distance[0][0]=1;
    
    q.push(Loc(0, 0));
    while(!q.empty()){
        Loc tmp=q.front();
        q.pop();
        for(int i=0; i<4; i++){
            int xx=tmp.x+dx[i];
            int yy=tmp.y+dy[i];
            if(xx>=0 && xx<row_size && yy>=0 && yy<column_size){
                if(maps[xx][yy]==1){
                    q.push(Loc(xx, yy));
                    maps[xx][yy]=0; // 다시 방문 안하도록
                    distance[xx][yy]=distance[tmp.x][tmp.y]+1;
                }
            }
        }
    }
    
    if(distance[row_size-1][column_size-1]!=0){
        return distance[row_size-1][column_size-1];
    } else{
        return -1;
    }
}