[프로그래머스] 게임 맵 최단거리 C++ 풀이 및 해설

https://school.programmers.co.kr/learn/courses/30/lessons/1844

프로그래머스

 

풀이 방법

간단히 BFS를 통해 풀 수 있는 문제이다.

미로의 크기가 최대 100x100이지만

방문 여부를 MAP을 사용하여 풀려고 했으나 사용했더니 효율성 부분에서 시간초과로 다 틀려버린다.

방문 여부를 그냥 2차원 배열을 통해 확인하도록 하자.

 

전체 코드

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

int solution(vector<vector<int>> maps)
{
    int answer = -1;
    queue<pair<int,pair<int,int>>> q; // (cnt,y,x)
    bool visit[100][100];
    fill(&visit[0][0], &visit[99][100], false);
    
    if(maps[0][0]==1) {
        q.push(make_pair(1,make_pair(0,0)));
        visit[0][0]=true;
    }
    
    
    while(!q.empty()){
        int x, y, cnt;
        cnt = q.front().first;
        x = q.front().second.second;
        y = q.front().second.first;
        q.pop();
        
        if(x==maps[0].size()-1 && y==maps.size()-1) {
            answer=cnt;
            break;
        }
        
        if(y-1>=0 && maps[y-1][x]==1 && visit[y-1][x]==false) {
            q.push(make_pair(cnt+1,make_pair(y-1,x)));
            visit[y-1][x]=true;
        }
        if(y+1<=maps.size()-1&&maps[y+1][x]==1 && visit[y+1][x]==false) {
            q.push(make_pair(cnt+1,make_pair(y+1,x)));
            visit[y+1][x]=true;
        }
        if(x-1>=0&&maps[y][x-1]==1 && visit[y][x-1]==false) {
            q.push(make_pair(cnt+1,make_pair(y,x-1)));
            visit[y][x-1]=true;
        }
        if(x+1<=maps[0].size()&&maps[y][x+1]==1 && visit[y][x+1]==false) {
            q.push(make_pair(cnt+1,make_pair(y,x+1)));
            visit[y][x+1]=true;
        }
        
    }
    
    return answer;
}

 

방문 여부를 MAP으로 사용한 코드 ( map 사용시 효율성 부분에서 시간초과남 )

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

int solution(vector<vector<int>> maps)
{
    int answer = -1;
    queue<pair<int,pair<int,int>>> q; // (cnt,y,x)
    map<pair<int,int>, bool> m; // 방문 여부
    
    
    if(maps[0][0]==1) {
        q.push(make_pair(1,make_pair(0,0)));
        m.insert({make_pair(0,0), true});
    }
    
    
    while(!q.empty()){
        int x, y, cnt;
        cnt = q.front().first;
        x = q.front().second.second;
        y = q.front().second.first;
        q.pop();
        
        if(x==maps[0].size()-1 && y==maps.size()-1) {
            answer=cnt;
            break;
        }
        
        if(y-1>=0 && maps[y-1][x]==1 && m.find(make_pair(y-1,x))==m.end()) {
            q.push(make_pair(cnt+1,make_pair(y-1,x)));
            m.insert({make_pair(y-1,x), true});
        }
        if(y+1<=maps.size()-1&&maps[y+1][x]==1 && m.find(make_pair(y+1,x))==m.end()) {
            q.push(make_pair(cnt+1,make_pair(y+1,x)));
            m.insert({make_pair(y+1,x), true});        
        }
        if(x-1>=0&&maps[y][x-1]==1 && m.find(make_pair(y,x-1))==m.end()) {
            q.push(make_pair(cnt+1,make_pair(y,x-1)));
            m.insert({make_pair(y,x-1), true});
        }
        if(x+1<=maps[0].size()&&maps[y][x+1]==1 && m.find(make_pair(y,x+1))==m.end()) {
            q.push(make_pair(cnt+1,make_pair(y,x+1)));
            m.insert({make_pair(y,x+1), true});
        }
        
    }
    
    return answer;
}