[프로그래머스] 미로 탈출 C++

 

다시 풀어보는 문제.

이번엔 정확성이 자꾸 틀려서.. 예전에 어떻게 풀었나 코드 보니

이번에 문제를 꼼꼼히 읽지 않았다. n x n 맵인줄 알았더니 row x col 맵이었다.

 

풀이는 마찬가지로 레버에서 bfs 돌면 된다.

#include <string>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

int mx[4] = {1, -1, 0, 0};
int my[4] = {0, 0, 1, -1};

bool visit[101][101];
int goal = 0;
bool sVisit, eVisit;

void bfs(int sx, int sy, int row, int col, vector<string>& maps) {
        
    queue<pair<pair<int, int>, int>> que;
    que.push({{sx, sy}, 0});
    visit[sx][sy] = true;
    
    
    while(!que.empty()) {
        
        int x = que.front().first.first;
        int y = que.front().first.second;
        int depth = que.front().second;
        
        que.pop();
        
        for(int i = 0; i < 4; i++) {
            int xx = x + mx[i];
            int yy = y + my[i];
        
        if(xx < 0 || xx >= row || yy < 0 || yy >= col) continue;
        
        
        if(!visit[xx][yy] && maps[xx][yy] != 'X') {
            que.push({{xx, yy}, depth + 1});
            visit[xx][yy] = true;
            
            if(maps[xx][yy] == 'S') {
                sVisit = true; goal += depth + 1;
            }
            if(maps[xx][yy] == 'E') {
                eVisit = true; goal += depth + 1;
            }
        }
      }
    }
}
    
int solution(vector<string> maps) {
    
    
    int row = maps.size();
    int col = maps[0].size();
    
    for(int i = 0; i < row; i++) {
        for(int j = 0; j < col; j++) {
           if(maps[i][j] == 'L') {
               bfs(i, j, row, col, maps);
               
               if(sVisit && eVisit) return goal;
               else return -1;
               
           }
        }
    }
}