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

처음에 BFS 깊이 우선 탐색으로 풀려다가 막막해서 다른 사람의 풀이를 참고했다.
https://ansohxxn.github.io/programmers/114/

[C++로 풀이] 게임 맵 최단거리 (BFS)⭐⭐

이분 참고함
1시간 투자해도 코드 완성이 안되면 그냥 바로 다른 코드 참고하는대신 복습하는 개인적인 룰이 있다.(변명변명)

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

struct Pos{
    int x;
    int y;
    Pos(int _x, int _y) {
        x = _x;
        y = _y;
    }
};
int solution(vector<vector<int>> maps)
{
    const int N = maps.size();
    const int M = maps[0].size();
    queue<Pos> q;
    
    vector<vector<int>> maps_dist(N,vector<int>(M)); //shortest distance vec
    
    vector<Pos> deltaCoord = {Pos(0,-1),Pos(1,0),Pos(0,1),Pos(-1,0)};
    //for the (0,0) first start
    maps_dist[0][0] = 1;
    q.push(Pos(0,0));
    maps[0][0] = 0;
    
    while(!q.empty()) {
        Pos current = q.front();
        q.pop();
        
        for(Pos delta : deltaCoord) {   //for all 4 direction
            Pos next_pos(current.x + delta.x, current.y + delta.y);
            //check effectiveness
            //1. check out of range
            if(next_pos.x < 0 || next_pos.y <0 || next_pos.x >= N || next_pos.y >= M)
                continue;
            //2. check can go there(already visit OR obstacle)
            if(maps[next_pos.x][next_pos.y] == 0)
                continue;
            
            q.push(next_pos);
            maps_dist[next_pos.x][next_pos.y] = maps_dist[current.x][current.y]+1;
            maps[next_pos.x][next_pos.y] = 0;
        }
    }
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            cout << maps_dist[i][j] << " ";
        }
        cout << endl;
    }
    // destination coord = (N-1,M-1)
    if(maps_dist[N-1][M-1] == 0)
        return -1;
    else
        return maps_dist[N-1][M-1];
}

첫 코드.
주어지는 맵이랑 똑같은 크기의 최단거리 맵을 만들어서 기록하고, 큐에 시작위치를 담고, maps에서 0으로 바꾼다음 큐가 빌때까지 루프를 돈다.
상하좌우 4방향에 대해서 유효성을 체크한다. 맵 바깥으로 가는 게 아닌지, 그 좌표의 값이 0이 아닌지(장애물 또는 이미 지나왔기에 0처리 된 경우)
이 유효성을 통과한다면 큐에 해당 다음 좌표를 넣고 현재 좌표는 0처리하고 다음 좌표의 최단거리를 현재 좌표의 최단거리+1로 갱신해준다.

모든 경로 탐색이 끝난 뒤 마지막 좌표의 값이 갱신되어있지 않다면 -1, 갱신되어있다면 그 값을 반환하게끔 한다.

정확성은 모두 맞췄는데, 효율성에서 0점이 나온다.
이미 통과한 다른 사람의 코드 풀이법을 훑은 다음에 내 방식을 적용하는 편이라 보통 풀이법이 보증되는 편이라 한방에 통과하던데 당황스러웠다.

효율성 올리기
내가 다르게 한 점을 생각해봤는데,

구조체 읽기를 자주 함 -> 이거때매 시간초과난다고 치면 구조체를 누가쓰겠음.. 이거때문이 아닐거임
방문 맵을 따로 만들지 않고 maps값을 0으로 만듦 -> 정확성은 맞으나 내가 생각하지 못한 부분에서 효율성이 떨어질수도(특정 조건을 캐치하지못해 중복체크를 자주한다던가의)
행,열이 표기법이 다름 -> 이거때매 시간초과날리가...

두번째 부분을 반영해서 해봤는데 역시나 시간초과 ㅠ
진짜 모르겠다. ㅠㅠㅠㅠㅠ 차이를 모르겠다고!!!

일단 나가야해서 저장 ㅜ 아 스트레스.



++ 알아냈음... 내 코드 체크를 위해서 maps_dist를 전체 출력하는 부분이 있는데 이거 안지우고 내서임
아..................... 내 시간
ㅠㅠㅠ
ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ
그치만 덕분에 문제 채점할때는 출력 다 지우고 하는 버릇이 제대로 박힐듯 ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ