✍️Today I Learned

📅 2025-10-27

• DFS vs BFS
• 프로그래머스: 미로탈출

---

DFS vs BFS

DFS

깊이 우선 탐색
한 방향으로 끝까지 들어가다 막히면 되돌아오는 방식으로 모든 경로를 탐색한다.
Stack이나 재귀 함수를 사용한다.
Last In First Out 구조

사용하는 경우

• 모든 경로를 탐색해야 할 때
• 조합 생성
• 경로의 개수 세기

BFS

너비 우선 탐색
시작점에서부터 같은 레벨의 범위를 한꺼번에 처리한다.
Queue를 사용한다.
Fisrt In First Out 구조

사용하는 경우

• 최단 거리를 구할 때
• 레벨별 탐색이 필요할 때

---

프로그래머스: 미로탈출

문제 링크
문제 설명
1 x 1 크기의 칸들로 이루어진 직사각형 격자 형태의 미로에서 탈출하려고 합니다. 각 칸은 통로 또는 벽으로 구성되어 있으며, 벽으로 된 칸은 지나갈 수 없고 통로로 된 칸으로만 이동할 수 있습니다. 통로들 중 한 칸에는 미로를 빠져나가는 문이 있는데, 이 문은 레버를 당겨서만 열 수 있습니다. 레버 또한 통로들 중 한 칸에 있습니다. 따라서, 출발 지점에서 먼저 레버가 있는 칸으로 이동하여 레버를 당긴 후 미로를 빠져나가는 문이 있는 칸으로 이동하면 됩니다. 이때 아직 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있습니다. 미로에서 한 칸을 이동하는데 1초가 걸린다고 할 때, 최대한 빠르게 미로를 빠져나가는데 걸리는 시간을 구하려 합니다.

미로를 나타낸 문자열 배열 maps가 매개변수로 주어질 때, 미로를 탈출하는데 필요한 최소 시간을 return 하는 solution 함수를 완성해주세요. 만약, 탈출할 수 없다면 -1을 return 해주세요.

제한사항

• 5 ≤ maps의 길이 ≤ 100
• 5 ≤ maps[i]의 길이 ≤ 100
• maps[i]는 다음 5개의 문자들로만 이루어져 있습니다.
  S : 시작 지점
  E : 출구
  L : 레버
  O : 통로
  X : 벽
• 시작 지점과 출구, 레버는 항상 다른 곳에 존재하며 한 개씩만 존재합니다.
• 출구는 레버가 당겨지지 않아도 지나갈 수 있으며, 모든 통로, 출구, 레버, 시작점은 여러 번 지나갈 수 있습니다.

풀이

DFS로 풀었다가 최단 거리를 보장하지 않는 문제때문에 BFS로 수정하고 레버를 찾고 길을 되돌아 가야하는 경우를 위해 경로 탐색을 2번으로 나눴다.

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

using namespace std;
struct Point
{
    int y;
    int x;
    int dist;
};

int bfs(int y, int x, char c, vector<string>& maps)
{
    queue<Point> q;
    vector<vector<bool>> visited(maps.size(),vector<bool>(maps[0].size()));
    
    q.push({y,x,0});
    visited[y][x] = true;
    
    int dy[]={-1,1,0,0};
    int dx[]={0,0,-1,1};
    
    while(!q.empty())
    {
        Point temp = q.front();
        q.pop();
        
        if(maps[temp.y][temp.x] == c)
        {
            return temp.dist;
        }
        
        for(int i=0; i<4; i++)
        {
            int tempY = temp.y+dy[i];
            int tempX = temp.x+dx[i];
            
            if(tempY>=0 && tempY<maps.size() && tempX>=0 && tempX<maps[0].size() 
               && !visited[tempY][tempX]
               && maps[tempY][tempX] != 'X')
            {
                visited[tempY][tempX] = true;
                q.push({tempY, tempX, temp.dist+1});
            }
        }
    }
    return -1;
}

int solution(vector<string> maps) {
    int answer = 0;
    vector<int> start(2,0);
    vector<int> lever(2,0);
    
    for(int i=0; i<maps.size(); i++)
    {
        for(int j=0; j<maps[0].size(); j++)
        {
            if(maps[i][j]=='S') start={i,j};
            if(maps[i][j]=='L') lever={i,j};
        }
    }
    
    int temp = 0;
    temp = bfs(start[0],start[1],'L', maps);
    if(temp==-1) return -1;
    answer += temp;
    
    temp =  bfs(lever[0],lever[1],'E', maps);
    if(temp==-1) return -1;
    answer += temp;
    
    return answer;
}

---

💡 느낀 점 (What I Felt)

문제에서 요구하는 것이 무엇인지에 따라 맞는 알고리즘을 먼저 골라야겠다.

---

출처 프로그래머스: 미로탈출