[프로그래머스] 미로 탈출 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;
               
           }
        }
    }
}

 

 

 

 

---

한번 더 풀었다.

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

using namespace std;

int N, M;

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

int S = 0, E = 0;

void bfs(int x, int y, vector<string>& maps) {
    
    queue<pair<int, int>> que;
    
    que.push({x, y});
    depth[x][y] = 0;
    
    while(!que.empty()) {
        
        int xx = que.front().first;
        int yy = que.front().second;
        
        if(maps[xx][yy] == 'S') S = depth[xx][yy];
        if(maps[xx][yy] == 'E') E = depth[xx][yy];
        
        que.pop();
        
        for(int i = 0; i < 4; i++) {
            
            int tx = xx + mx[i];
            int ty = yy + my[i];
            
            if(tx < 0 || tx >= N || ty < 0 || ty >= M) continue;
            
            
            if(depth[tx][ty] == -1 && maps[tx][ty] != 'X') {
                // 아직 가지 않은 곳이면서 X가 아닌 곳
                que.push({tx, ty});
                depth[tx][ty] = depth[xx][yy] + 1;
            }
            
        }
        
    }
    
}

int solution(vector<string> maps) {
    int answer = 0;
    
    N = maps.size();
    M = maps[0].length();
    memset(depth, -1, sizeof(depth));
    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            if(maps[i][j] == 'L') {
                bfs(i, j, maps);
            }
        }
    }
    
    return S > 0 && E > 0 ? S + E : -1;
}