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

✅ LV. 2
🔖 BFS

✏️ 1차 솔루션

DFS 로 접근

1. 동서남북 방향으로 이동
2. Out Of Index 처리
3. 해당 블럭이 벽이면 return
4. 이미 방문한 블럭 표시
5. 마지막 노드에 도달하면 최소값으로 answer 갱신

🚨 1차 trouble

1. 최단거리를 구하는 방법이 필요한데 DFS 로 접근할 경우, 경로를 찾아갈 수는 있지만 최단거리를 구하는 방법에 적합한지는 잘 모르겠음.
2. 재귀함수를 통해 이미 지나간 경로를 지나와야하는데 그럴 경우, 이미 방문한 노드를 표시해두기 어려움
3. 다음에 탐색할 노드, 현재까지의 경로값 저장해두면서 관리해야하는데 골치 아픔

✏️ 2차 솔루션

BFS 로 접근
풀이 방식은 DFS 와 유사하지만 큐를 사용해서 풀이

1. 초기화: 큐에 처음 시작 노드인 (0,0) push
2. 단순히 방문여부만 저장하는 것이 아니라 각 노드의 경로값(dist) 저장 ➡️ dist 에 저장한 값이 0 이 아니라면 방문했던 노드로 판단

큐 empty 시점까지 계속 반복

1. 큐의 front 인덱스를 현재 위치로 저장하고 pop
2. 현재 위치에서 갈 수 있는 노드의 인덱스를 큐에 push
3. 큐에 push 한 인덱스의 dist 값을 현재 위치의 dist 값에 1을 더해 저장해둠

🔗 [C++] 큐

✏️ 2차 코드

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

int solution(vector<vector<int> > maps)
{
    int answer = 0;
    int cnt=1;
    int dist[10000][10000];
    queue<pair<int,int>> q;
    q.push(make_pair(0,0));
    dist[0][0]=cnt;
    
    int mov[4][2]={{1,0},{0,1},{-1,0},{0,-1}};    
    
    while(!q.empty()) {
        int y=q.front().first;
        int x=q.front().second;

        if(y==maps.size()-1&&x==maps[0].size()-1) {
            if(answer==0) answer=dist[y][x];
            else answer=min(answer,dist[y][x]);
        }
        
        q.pop();
        cnt=dist[y][x];
        
        for(int i=0;i<4;i++) {
            int yq=y+mov[i][0];
            int xq=x+mov[i][1];
            if(yq<0||xq<0||yq>=maps.size()||xq>=maps[0].size()) continue;
            
            if(dist[yq][xq]==0  && maps[yq][xq]==1) {
                q.push(make_pair(yq,xq));
                dist[yq][xq]=++cnt;
            }

        }
        
    }
    
    if(answer==0) answer=-1;

    
    return answer;
}

🚨 2차 trouble

자꾸 효율성 오류가 난다,,거의 통과 못함

• 변수가 너무 많은 듯하다
• out of index 처리도 일단 다음 노드로 이동한 후에 처리하던가 애초에 이동조차 못하게 사전 방지하던가 한가지로 통일이 필요

✏️ 최종 솔루션

• code 정리하기
• 경로값 저장해둔 dist 를 배열로 구현했더니 메모리 낭비가 발생하는 것으로 보여서 벡터로 변환
• 가로, 세로 값 별도로 저장해서 관리

🔗 [C++] 2차원 vector 초기화

✏️ 최종 코드

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

int solution(vector<vector<int> > maps)
{
    int answer = 0;

    queue<pair<int,int>> q;
    q.push(make_pair(0,0));
    
    int yy=maps.size();
    int xx=maps[0].size();
    
    vector<vector<int> > dist(yy, vector<int>(xx, 0));
    dist[0][0]=1;
    
    int mov[4][2]={{1,0},{0,1},{-1,0},{0,-1}};    
    
    while(!q.empty()) {
        
        int y=q.front().first;
        int x=q.front().second;
        
        q.pop();
        
        for(int i=0;i<4;i++) {
            int yq=y+mov[i][0];
            int xq=x+mov[i][1];
            
            //Out of idx
            if(yq<0||xq<0||yq>=yy||xq>=xx) continue;

            //이미 지난 경로이거나 벽일 경우
            if(maps[yq][xq]==0 || dist[yq][xq]>0) continue;
             
            q.push(make_pair(yq,xq));
            dist[yq][xq]=dist[y][x]+1;
            
        }
        
        
        
    }
    
    if(dist[yy-1][xx-1]==0) return -1;
    else return dist[yy-1][xx-1];

}