[Lv.2] 게임 맵 최단거리

출처. 프로그래머스

 

DFS/BFS에 해당 하는 문제로 문제 자체는 어렵지 않았다.

 

나는 접근을 DFS로 생각하여 모든 루트를 다 돌고나서 최소거리를 반환하는 식으로 코드를 구현하였다.

#include <vector>
#include <iostream>
using namespace std;

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

size_t n, m;
int ret = -1;
vector<vector<int>> map;

void moving (int y, int x, int cnt) {
    if (x == (n-1) && y == (m-1)) {
        if (ret == -1) {
            ret = cnt;
            return ;
        }
        
        if (ret > cnt)
            ret = cnt;
        return ;
    }
    
    for (size_t idx = 0 ; idx < 4 ; idx++) {
        int ny = y + dy[idx];
        int nx = x + dx[idx];
        
        if (0 <= nx && nx < n && 0 <= ny && ny < m) {
            if (map[ny][nx] == 1) {
                vector<vector<int>> temp;
                
                temp = map;
                map[ny][nx] = 0;
                moving(ny, nx, cnt + 1);
                map[ny][nx] = 1;
                map = temp;
            }
        }
    }
}

int solution(vector<vector<int> > maps)
{
    n = maps.at(0).size();
    m = maps.size();
    
    map = maps;
    
    map[0][0] = 0;
    moving(0, 0, 1);
    
    return ret;
}

 

하지만 결과는 테스트 케이스는 통과했으나, 효율성에서 0점...

 

생각해보니, 최단거리를 찾는 문제에서는 목적지에 도달하는 순간이 최소값이 나오는 BFS가 적절하다고 판단되어 코드를 BFS로 수정하였다.

#include <vector>
#include <queue>
#include <iostream>
using namespace std;

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

int solution(vector<vector<int>> maps)
{
    // 입력 maps의 가로, 세로 저장
    size_t n = maps.at(0).size();
    size_t m = maps.size();
    
    // 다음 좌표를 기억할 큐 생성
    queue<pair<int,int>> nextPos;
    maps[0][0] = 0; // 현재위치를 벽으로 설정
    nextPos.push({0,0}); // 처음 출발지 등록
    
    int ret = 0; // 반복자 카운터 설정
    bool isFindDest = false; // 목적지 찾았니?
    
    // 다음좌표 큐가 빌었고 목적지를 찾을때까지 반복
    while (!nextPos.empty() && !isFindDest) {
        ret++;
        size_t loop = nextPos.size(); // 현재 큐에 들어있는 좌표만큼만 반복하기 위해서 초기화
        
        for (size_t idx = 0 ; idx < loop ; idx++) {
            pair<int,int> curPos = nextPos.front(); nextPos.pop();  // 맨 앞에 있는 좌표 꺼내고, pop
            
            for (size_t cnt = 0 ; cnt < 4 ; cnt++) {
                int ny = curPos.first + dy[cnt];
                int nx = curPos.second + dx[cnt];
                
                if (0<=nx && nx < n && 0<=ny && ny < m && (maps[ny][nx] != 0)) {
                    // 다음좌표가 0보다 크고 맵의 가로, 세로보다 작고 벽이 아닌경우에는 다음좌표로 이동
                    nextPos.push({ny, nx});
                    maps[ny][nx] = 0;
                    
                    if (ny == (m-1) && nx == (n-1)) { // 혹시 다음 지점이 목적지?
                        isFindDest = true;
                        ret++;
                        break; // 그럼 끝내!
                    }
                }
            }
        }
    }
    
    if (!isFindDest) // 목적지를 찾지 못했다면, -1로 결과설정
        ret = -1;
    
    return ret;
}