정올 3432 드론(drone)

algorithm : BFS, dp

 

이문제는 백준에 없으므로 정올에서 채점 가능

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2754&sca=90 

JUNGOL

해설

각 숫자 위치마다 BFS를 돌려 자기위치에서 다른 숫자 까지 가는 거리를 구한다.

S를 돌아가면서 답이 될수 있는 것을 dp에 넣음

dp[T + 1]에서 최소값이답

 

#include<bits/stdc++.h>
#define LM 550+10
#define INF 199999999
using LL = long long;
using namespace std;
 
int N,M,T;
int A,B,C,num1,num2,cnt = 1,ans = INF;
int arr[LM][LM],visit[LM][LM];
int chk[LM][LM];
int S[1000 + 10];
int Dist[LM][LM];
int Dx[16][4] = {{1,0,-1,0},{1,0,-1,0},{0,0,-1,0},{0,0,-1,0},{1,0,-1,0},{1,0,-1,0},{0,0,-1,0},{0,0,-1,0},{1,0,0,0},{1,0,0,0},{0,0,0,0},{0,0,0,0},{1,0,0,0},{1,0,0,0},{0,0,0,0},{0,0,0,0,}};
int Dy[16][4] = {{0,1,0,-1},{0,1,0,0},{0,1,0,-1},{0,1,0,0},{0,0,0,-1},{0,0,0,0},{0,0,0,-1},{0,0,0,0},{0,1,0,-1},{0,1,0,0},{0,1,0,-1},{0,1,0,0},{0,0,0,-1},{0,0,0,0},{0,0,0,-1},{0,0,0,0}};
int dp[1000 + 10][200];
struct data{
    int x,y,vel;
};
struct data1{
    int x,y,dist;
};
struct data2{
    int num,pos,ans;
};
vector<data> v;
queue<data1> que[LM];
void input(){
    scanf("%d",&N);
    for(int i = 1 ; i <= N ; i++){
        for(int j = 1 ; j <= N ; j++)
            scanf("%d",&arr[i][j]);
    }
    scanf("%d",&M);
    v.push_back({0,0,0});
    v.push_back({1,1,0});
    num1 = 1;
    num2 = M + 2;
    chk[1][1] = 1;
    chk[N][N] = M + 2;
    for(int  i = 1 ; i <= M ; i++){
        scanf("%d %d %d",&A,&B,&C);
        v.push_back({B,A,C});
        chk[A][B] = i + 1;
        if(A == 1 && B == 1) num1 = i + 1;
        if(A == N && B == N) num2 = i + 1;
    }
    v.push_back({N,N,101});
    scanf("%d",&T);
    for(int i = 1 ; i <= T ; i++)
        scanf("%d",&S[i]);
}
 
void Push(int x,int y,int dist){
    if(visit[y][x] == cnt || x < 1 || y < 1 || N < x || N < y)return;
    visit[y][x] = cnt;
    que[cnt].push({x,y,dist});
}
void BFS(){
    for(int i = 1; i < v.size() ; i++,cnt++){
        Push(v[i].x,v[i].y,0);
        while(!que[i].empty()){
            auto t = que[i].front();
            que[i].pop();
            if(chk[t.y][t.x] != 0)
                Dist[i][chk[t.y][t.x]] = t.dist;
            for(int j = 0 ; j < 4 ; j++)
                Push(t.x + Dx[arr[t.y][t.x]][j],t.y + Dy[arr[t.y][t.x]][j],t.dist + 1);
        }
    }
}
void Electronic_board(){
    for(int i = 0 ; i < v.size() ; i++) dp[0][i] = INF;
    dp[0][1] = 0;
    S[0] = 0,S[T + 1] = 101;
    for(int i = 1 ; i <= T + 1; i++){
        for(int j = 1 ; j < v.size() ; j++){
            dp[i][j] = INF;
            if(S[i] == v[j].vel){
                for(int k = 1 ; k < v.size() ; k++){
                    if(k == 1) dp[i][j] = min(dp[i][j],dp[i - 1][1] + Dist[j][num1]);
                    else if(k == v.size() - 1) dp[i][j] = min(dp[i][j],dp[i - 1][v.size() - 1] + Dist[j][num2]);
                    else dp[i][j] = min(dp[i][j],dp[i - 1][k] + Dist[j][k]);
                }
            }
        }
    }
    for(int i = 1; i < v.size() ; i++)
        ans = min(ans,dp[T + 1][i]);
}
 
int main(){
    //freopen("input.txt","r",stdin);
    input();
    BFS();
    /**
    for(int i = 0 ; i < v.size() ; i++){
        for(int j =  0 ; j < v.size() ; j++)
            printf("%d ",Dist[i][j]);
        printf("\n");
    }**/
    //printf("\n");
    Electronic_board();
    //for(int i = 0 ; i < 4 ; i++)
        //printf("%d %d\n",1 + Dx[C][i],1 + Dy[C][i]);
    printf("%d",ans + 2);
    return 0;
}