미로 탈출(30분)

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

구현 아이디어 3분 구현 27분

풀이

한 칸을 이동하는데는 1초가 걸린다. 최소 시간을 구하는 문제이기 때문에 BFS를 활용하여 풀었다.

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

using namespace std;

struct Data
{
    int i, j, sum;
    Data(int i, int j, int sum)
    {
        this->i = i;
        this->j = j;
        this->sum = sum;
    }
};

int ch[100][100];

int solution(vector<string> maps) {
    int answer = 0;
    
    bool blever = false, bgoal = false;
    int N = maps.size();
    int M = maps[0].size();
    
    queue<Data> Q;
    
    for(int i = 0; i < N; ++i)
    {
        for(int j = 0; j < M; ++j)
        {
            if(maps[i][j] == 'S') Q.push(Data(i, j, 0));
            else if(maps[i][j] == 'X') ch[i][j] = 1;
        }
    }
    
    int di[4] = {-1, 0, 1, 0};
    int dj[4] = {0, 1, 0, -1};
    
    while(!Q.empty())
    {
        Data cur = Q.front();
        Q.pop();
        
        if(!blever && maps[cur.i][cur.j] == 'L')
        {
            while(!Q.empty()) Q.pop();
            
            for(int i = 0; i < N; ++i)
            {
                for(int j = 0; j < M; ++j)
                {
                    if(maps[i][j] == 'X') ch[i][j] = 1;
                    else ch[i][j] = 0;
                }
            }
            blever = true;
        }
        else if(blever && !bgoal && maps[cur.i][cur.j] == 'E')
        {
            bgoal = true;
            answer = cur.sum;
            break;
        }
        
        for(int i = 0; i < 4; ++i)
        {
            int rr = cur.i + di[i];
            int cc = cur.j + dj[i];
            
            if(rr < 0 || cc < 0 || rr >= N || cc >= M || ch[rr][cc] == 1) continue;
            Q.push(Data(rr, cc, cur.sum + 1));
            ch[rr][cc] = 1;
        }
    }
    
    if(!bgoal) answer = -1;
    
    return answer;
}