[프로그래머스] 미로 탈출 문제 풀이 c++

BFS문제의 변형이다.

시작지점에서 레버까지의 BFS로 최소거리를 구하고, 레버에서 출구까지 BFS로 최소거리를 구하면 된다

 

우선 maps를 전체 탐색하여 시작지점과 출구의 위치를 구한다.

큐를 2개 쓰거나, 반복문을 새로 시작하는 방법도 있었지만 반복문 하나에서 큐1개로 해결하기 위해 ck라는 변수를 활용했다.

S->L로 가는 동안 visit체크는 maps에 V를 표시하고 L에 도달하면 ck를 W로 바꿔서 W로 visit 체크를 한다.

L에 도달하기 전에 E에 먼저 도달한 경우는 L을 만나서 ck가 W로 바꿔야 레버를 먼저 동작시킨 것이므로 ck가 W일때만 출구에 도달한 것이 된다.

 

 

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

using namespace std;

struct Pos{
  int x;
  int y;
  int cnt;
  Pos(int a, int b, int c){
    x = a; y = b; cnt = c;
  }
};

int solution(vector<string> maps) {
    Pos start(0,0,0), end(0,0,0);

    for(int i=0; i<maps.size(); i++){
      for(int j=0; j<maps[0].size(); j++){
        if(maps[i][j] == 'S'){
          start.x = i; start.y = j;
        }
        else if(maps[i][j] == 'E'){
          end.x = i; end.y = j;
        }
      }
    }

    queue<Pos> q;
    q.push(start);

    int moves[4][2] = {{0,1}, {1,0}, {-1,0}, {0,-1}};
    char ck = 'V';
    while(!q.empty()){
      int x = q.front().x;
      int y = q.front().y;
      int cnt = q.front().cnt;

      for(int i=0; i<4; i++){
        int nx = x + moves[i][0];
        int ny = y + moves[i][1];
        int ncnt = cnt + 1;
        if(nx>=0 && nx<maps.size() && ny>=0 && ny<maps[i].size() && maps[nx][ny] != 'X' && maps[nx][ny] != ck){
          if(maps[nx][ny] == 'L'){
            while(!q.empty()) q.pop();
            q.push(Pos(x,y,cnt));
            q.push(Pos(nx,ny,ncnt));
            ck = 'W';
            maps[nx][ny] = ck;
            break;
          }
          else if(nx == end.x && ny == end.y && ck =='W'){
            return ncnt;
          }
          else{
            q.push(Pos(nx,ny,ncnt));
            maps[nx][ny] = ck;
          }
        }
      }
      q.pop();
    }    
    return -1;
}

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