프로그래머스 게임 맵 최단거리 c++ (dfs, bfs)

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

프로그래머스

재귀적 사고가 필요한 과제를 하고 있어서 dfs로 풀었다. 바로 시간초과

#include<vector> // 시간초과 dfs
using namespace std;

vector<vector<int> > map, visit;
int cnt = 0;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

void    dfs(int x, int y, int depth) {
    if (x == map.size() - 1 && y == map[0].size() - 1) {
        if (cnt == 0 || depth < cnt)
            cnt = depth;
        return ;
    }
    visit[x][y] = 0;
    for (int i = 0; i < 4; i++) {
        int curX = x + dx[i];
        int curY = y + dy[i];
        if (curX < map.size() && curX >= 0
            && curY < map[0].size() && curY >= 0
            && visit[curX][curY] == 1)
            dfs(curX, curY , depth + 1);
    }
    visit[x][y] = 1;
}

int solution(vector<vector<int> > maps)
{
    map = maps;
    visit = maps;
    
    dfs (0, 0, 0);
    if (cnt == 0)
        return -1;
    return (cnt + 1);
}

#include<vector> // 통과 bfs
#include <queue>
#include <cstdlib>
using namespace std;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

int solution(vector<vector<int> > maps)
{
    int visit[100][100];
    for (int i = 0; i < 100; i++)
        for (int j = 0; j < 100; j++)
            visit[i][j] = 0;
    queue<pair<int, int> > q;
    int row = maps.size();
    int col = maps[0].size();
    
    visit[0][0] = 1;
    q.push(make_pair(0, 0));
    while (!q.empty()) {
        int curX = q.front().first;
        int curY = q.front().second;
        q.pop();
        
        if (curX == row - 1 && curY == col - 1)
            return (visit[curX][curY]);
        
        for (int i = 0; i < 4; i++) {
            int nextX = curX + dx[i];
            int nextY = curY + dy[i];
            
            if (nextX >= 0 && nextX < row && nextY >= 0 && nextY < col 
                && maps[nextX][nextY] == 1 && visit[nextX][nextY] == 0) {
                q.push(make_pair(nextX, nextY));
                visit[nextX][nextY] = visit[curX][curY] + 1;
            }
        }
    }
    return (-1);
}

 

평소에 재귀를 어려워 했어서 bfs로 풀 수 있는 문제는 죄다 bfs로 풀다보니 이런 경우는 처음 겪어봤다.  이 문제에선 최단 경로를 찾아야 하므로 모든 노드를 하나씩 최대한 깊게 파는 dfs는 비효율적이다. 그냥 무지성으로 bfs써야지 ㅎㅎ했단 쓰레기... 이젠 효율적인 알고리즘을 찾아 사용하는 멋쟁이 개발자가 되어보자