level 2 게임 맵 최단거리 (BFS)

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

코딩테스트 연습 - 게임 맵 최단거리

 

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

using namespace std;

struct POSI {
    int y, x, t;
};

// BFS
vector<vector<int> > arr;
int answer = 987654321;
// x, y
int n, m;
const int dy[4] = {0, 0, -1, 1};
const int dx[4] = {-1, 1, 0, 0};

bool visit[110][110];

queue <POSI> q;

void BFS(POSI start) {
    
    q.push(start);
    visit[start.y][start.x] = true;
    
    while(!q.empty()) {
        POSI cur = q.front();
        q.pop();
        
        if(cur.y == m-1 && cur.x == n-1) {
            answer = cur.t;
            return;
        }
        
        for(int i=0; i<4; i++) {
            POSI next;
            next.y = cur.y + dy[i];
            next.x = cur.x + dx[i];
            next.t = cur.t + 1;

            if(next.y < 0 || next.y >= m || next.x < 0 || next.x >= n)
                continue;
            
            if(visit[next.y][next.x] == false && arr[next.y][next.x] == 1) {
                visit[next.y][next.x] = true;
                q.push(next);
            }
        }
    }

}


int solution(vector<vector<int> > maps)
{
    arr = maps;
    m = maps.size(); // y
    n = maps[0].size(); // x
    
    POSI start;
    start.y = 0; start.x = 0; start.t = 1;
    
    BFS(start);
    
    if (answer == 987654321)
        return -1;
    
    return answer;
}

 

 

BFS 로 최단거리 풀기.

DFS 는 처음으로 나온 값이 최단 경로라는 확신이 없음.

-> 시간복잡도를 줄일 수 있음

 

처음 DFS 로 접근했다가 효율성 테스트 통과 실패