[C++] level2 게임 맵 최단거리 1844

📌게임 맵 최단거리

/*문제 풀이가 사진이 조금 많아 생략. 링크로 들어가서 볼 수 있음!*/

📌풀이

먼저 보자마자 BFS를 이용하여 최단 거리를 구해야겠다는 생각이 들었다!

1. BFS 시 방문여부 체크와, 상하좌우 이동에 필요한 좌표를 전역변수로 생성

   bool visit[101][101] = {false, }; //방문여부 체크
   //상 하 좌 우
   int row[4] = {0, 0, -1, 1};
   int col[4] = {1, -1, 0, 0};

2. BFS 탐색하면서 쓸 queue 생성
   queue는 다음과 같이 frist에는 x, y의 좌표를 second에는 길이를 담도록 하였다.

   queue<pair<pair<int, int>, int>> q;

3. 로직
   다음 거리 = 현재 거리 + 1 해서 다시 큐에 담는 형태

그러므로 탐색하려는 x, y가 maps의 마지막이라면 현재 거리를 return

1. 먼저 큐를 생성 후 출발좌표(0,0)과 시작거리(1)을 담고 시작한다.
2. 큐가 빌 때까지 다음 과정을 반복한다.
  2-1. 큐의 맨 처음 값으로 현재 x, y, 거리를 구한 후 큐에서 뺀다.
  2-2. 만약 현재 x, y가 maps의 마지막이라면 현재 거리를 return한다. 
  2-3. 상하좌우로 탐색하며 다음 x, y, 거리를 구해 큐에 넣는다.
     2-3-1. 다음 거리는 현재거리 + 1 이다.
     2-3-2. 다음 x, y의 좌표가 현재 maps의 n과 m을 넘으면 continue
     2-3-3. 다음 x, y의 좌표가 아직 방문하지 않았으며 벽이 아닌 길이라면(1) 큐에 넣고 방문여부를 체크한다.

📌코드

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

bool visit[101][101] = {false, };
//상 하 좌 우
int row[4] = {0, 0, -1, 1};
int col[4] = {1, -1, 0, 0};

int solution(vector<vector<int> > maps)
{
    int width = maps.size(); //n
    int height = maps[0].size(); //m

    queue<pair<pair<int, int>, int>> q; //first.first : x, first.second : y, second : distance
    //출발 (0, 0) 시작거리는 1
    q.push({{0, 0}, 1});
    visit[0][0] = true;

    while(!q.empty()){
        int cur_x = q.front().first.first;
        int cur_y = q.front().first.second;
        int cur_dist = q.front().second;
        q.pop();

        //현재 x, y가 maps의 마지막이라면
        if(cur_x == width - 1 && cur_y == height - 1) return cur_dist;

        // 상 하 좌 우로 탐색
        for(int i = 0; i < 4; i++){
            int next_x = cur_x + row[i];
            int next_y = cur_y + col[i];
            int next_dist = cur_dist + 1; 

            //범위에 해당 안된다면
            if(next_x < 0 || next_x >= width || next_y < 0 || next_y >= height) continue;

            //아직 방문하지 않았고, 벽이 아닌 길이라면
            if(!visit[next_x][next_y] && maps[next_x][next_y] == 1){
                q.push({{next_x, next_y}, next_dist});
                visit[next_x][next_y] = true;
            }
        }
    }

    return -1;  //범위 내에서 거리를 구하지 못했다면
}

회고

• 처음에 시간 초과가 발생했다.
  • 범위 체크하는 것을 함수로 만들고, bfs 전체를 함수로 만들었는데 이게 문제인 것 같아 그냥 솔루션에서 다하는 걸로 수정햇다.
  • width나 height 변수로 따로 빼지 않고, 매 범위 체크 시 maps.size(), maps[0].size()를 했다. 이게 문제인 것 같아서 따로 변수로 빼두었다.

---

• 궁금한 점 1) 정말 함수로 빼놔서 시간초과가 발생한건가? 그렇다면 왜?

---