LV.2 미로탈출

https://school.programmers.co.kr/learn/courses/30/lessons/159993?language=cpp

프로그래머스

 

DFS와 BFS 중 BFS를 사용한 이유

 

DFS는 기핑 우선 탐색으로 한 경로를 끝까지 따라간다.

BFS는 어비 우선 탐색으로 가까운 노드부터 탐색한다.

자료구조 사용은

DFS는 stack을 사용하는 것이 적합하며

BFS는 queue를 사용하는 것이 적합하다.

 

BFS는 최단 거리 검색, 최소 이동 횟수에 적합하다.

DFS는 모든 경로 참색, 백트래킹에 적합하다.

 

 

전반적인 로직

1. S - L 까지의 거리를 구한다.

2. L - E 까지의 거리를 구한다.

3. 해당 거리를 더하여 출력한다.

 

거리 구하기 로직

1. 4방향을 갈 수 있는 dx, dy 배열 두 개를 둔다.

2. queue(컨테이너 어댑터)를 이용하여 queue가 빌 때 까지 계산한다.

3. 현재 위치에서 상하좌우를 확인하여

3-1. 맵의 범위를 벗어나지 않고

3-2. 벽이 아니며,

3-3 아직 방문하지 않은 곳이라면

큐에 추가하고 방문 처리를 한다.

4. 목표를 만났다면 현재 거리의 time을 반환한다.

5. 끝까지 탐색해도 도달하지 못했다면 -1을 반환한다.

 

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

using namespace std;


int bfs(vector<string>& maps, pair<int,int> start, char target)
{
    int n = maps.size();
    int m = maps[0].size();
    vector<vector<int>> visited(n, vector<int>(m,0));
    
    int dx[4] = {1,-1,0,0};
    int dy[4] = {0,0,1,-1};
    
    queue<pair<int,int>> q;
    q.push(start);
    visited[start.first][start.second] = 1;
    
    int time = 0;
    while(!q.empty())
    {
        int size = q.size();
        while (size--)
        {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            
            if(maps[x][y] == target)
                return time;
            
            for (int i = 0; i < 4; i++)
            {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(nx >= 0 && nx < n && ny >= 0 && ny < m &&
                  !visited[nx][ny] && maps[nx][ny] != 'X')
                {
                    visited[nx][ny] = 1;
                    q.push({nx,ny});
                }
            }
        }
        time++;
    }
    
    return -1;
}

int solution(vector<string> maps) {
    int answer = 0;
    
    pair<int,int> start, lever, exit;
    int n = maps.size();
    int m = maps[0].size();
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (maps[i][j] == 'S') start = {i, j};
            else if (maps[i][j] == 'L') lever = {i, j};
            else if (maps[i][j] == 'E') exit = {i, j};
        }
    }

    int toLever = bfs(maps, start, 'L');
    if (toLever == -1) return -1;

   int toExit = bfs(maps, lever, 'E');
    if (toExit == -1) return -1;    
    
    return toLever + toExit;
}