[백준]늑대 사냥꾼(2917)

문제 링크 : [백준]늑대 사냥꾼(2917)

문제 설명

N * M 의 배열이 아래와 같은 내용으로 주어집니다.

• V : 출발 지점
• J : 도착 지점
• . : 빈칸
• + : 나무

V에서 출발하여, J까지 도착하는데, 최대한 나무에서 멀리 떨어져서 도착하려고 합니다.
이때 이동구간 중 나무와 제일 가까이 있는 거리를 구하세요.

입력

N M(배열 크기, 1 <= N, M <= 500)
C_ij(배열 내용, 문제 설명 참조)

4 4
+...
....
....
V..J

출력

3

카테고리

#다익스트라 #BFS

시간 복잡도 상한

O(N * M * logN*M)

해결 방법

1. 각 지점마다 나무까지의 거리를 알아야하기 때문에 지점별로 나무까지의 거리를 구합니다.
2. 입력을 받으면서 나무를 만날 때마다 나무 정보를 큐에 넣습니다.
3. BFS를 돌면서 모든 지점에서 가장 가까운 나무까지의 거리를 구합니다.
4. 시작점에서 도착점까지 가는 최단거리(최소비용)을 구하면 되는데, 그 최소비용이 일반적인 거리가 아닌 나무까지의 최소거리가 됩니다.
5. 다익스트라에서 우선순위 큐를 이용할 때, 정렬 기준은 아래와 같습니다.
   5-1. 특정 지점에서 나무까지 거리를 내림차순으로 정렬해야 합니다.
   5-2. 모든 구간 중 최소비용을 구하기 때문에, 현재 엣지의 도착지점의 나무까지의 거리가 아닌 출발점부터 도착지점까지 모든 구간의 나무까지의 거리를 대상으로 합니다.
6. 다익스트라와 동일하지만 우선순위 큐의 정렬 기준을 5처럼 설정하면 됩나다.

시간복잡도

O(N² * log(N²))

코드

#include<cstdio>
#include<queue>
#include<algorithm>
#include<string.h>
#define N 501
#define f first
#define se second
using namespace std;
typedef pair<int,int>P;
typedef pair<int,P>R;
int n,m,d[N][N],e[N][N],i,j,o[4][2]={{1,0},{0,1},{-1,0},{0,-1}},a,b,s1,s2;
char s[N][N];
queue<P>w;
priority_queue<R>q;
int va(int x,int y){
    return x>=0&&y>=0&&x<n&&y<m;
}
int main(){
    scanf("%d%d",&n,&m);
    for(;i<n;i++){
        scanf("%s",s[i]);
        for(j=0;j<m;j++){
            if(s[i][j]=='+')w.push({i,j}),e[i][j]=1;
            if(s[i][j]=='V')s1=i,s2=j;
        }
    }
    while(!w.empty()){
        P c=w.front();w.pop();
        for(i=0;i<4;i++){
            a=c.first+o[i][0];b=c.second+o[i][1];
            if(va(a,b)&&!e[a][b])e[a][b]=d[a][b]=d[c.first][c.second]+1,w.push({a,b});
        }
    }
    memset(e,0,sizeof(e));
    q.push({d[s1][s2],{s1,s2}});
    while(!q.empty()){
        R c=q.top();q.pop();
        s1=c.se.f;s2=c.se.se;
        if(e[s1][s2])continue;
        if(s[s1][s2]=='J'){
            printf("%d",c.f);
            break;
        }
        e[s1][s2]=1;
        for(i=0;i<4;i++){
            a=s1+o[i][0];b=s2+o[i][1];
            if(va(a,b)&&!e[a][b])q.push({min(c.f,d[a][b]),{a,b}});
        }
    }
}