[틀림] 프로그래머스 보물지도 // 3차원 bfs

https://school.programmers.co.kr/learn/courses/15009/lessons/121690?language=cpp

프로그래머스

* 풀이

최단거리는 bfs

상태 : { y, x, 점프사용여부, dist }

단순한 bfs는 vis를 방문여부용도 && 거리용도로 사용, but 복잡한경우 dist라는 상태를 따로 분리하는게 좋겠다.

이문제는 앞쪽에서 방문여부체크, 종료조건을 체크하는 bfs가 유리.

bfs는 먼저 도착한게 최단거리다.

3차원 bfs 이해하기

세계를 2개로 나눠서 그려보자.

세계간 이동가능 여부를 그려보자.

공통) +-1로 이동가능

안쓴경우 ) +-2로도 이동가능

#include <bits/stdc++.h>

using namespace std;

const int INF=987654321;
int ret=-1;
// vector<vector<int>> Hole;
int Hole[1004][1004], vis[1004][1004][2];
int dp[1004][1004][4];
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
int N,M;

struct A{
    int y, x, used, dist;
};

int solution(int n, int m, vector<vector<int>> hole) {
    // Hole=hole;
    fill(&dp[0][0][0], &dp[0][0][0]+1004*1004*4,INF);
    N=n;N--;
    M=m;M--;
    for(auto v : hole){
        Hole[v[0]-1][v[1]-1]=1;
    }
    // ret = dfs(0,0,0);
    
    queue<A> q;
    // vis[0][0][0]=1;
    q.push({0,0,0,0});
    
    while(q.size()){
        auto cur = q.front(); q.pop();
        int y = cur.y;
        int x = cur.x;
        int used = cur.used;
        int dist = cur.dist;
        // cout<<y<<" "<<x<<" "<<dist<<"\n";
        if(y==N && x==M){
            ret=dist;
            break;
        }
        if(y>N || x>M || y<0 || x<0){
            continue;
        }
        if(Hole[y][x]) continue;
        if(vis[y][x][used]) continue;
        
        vis[y][x][used]=1;
        for(int i=0;i<4;++i){
            int ny = y+dy[i];
            int nx = x+dx[i];
            q.push({ny,nx,used, dist+1});
            
            // 안썻다면, 사용가능
            if(!used){
                int ny = y+dy[i]*2;
                int nx = x+dx[i]*2;
                q.push({ny,nx,1,dist+1});
            }
        }
    }
    
    return ret;
}

 

 

시간복잡도

8(기존4방향 + 점프4방향) ^ 1000 * 1000 ? 이경우는 기존의 방문한 셀을 재방문 가능한경우의 시간복잡도이다.

이문제는 재방문 불가이므로, 8 * 1000 * 1000 이다. 각 셀당 8방향 탐색가능

따라서, dp 사용이 필요없다. 

bfs에 dp 도 가능한가? dfs로만 해봐서 학습필요.