[백준] 16930 - 달리기 (c++)

https://www.acmicpc.net/problem/16930

 

문제 요약

N*M크기의 격자모양 체육관이 있다. 각 칸은 빈칸 아니면 벽이다. 

진영이는 1초마다 방향을 하나 골라서 그 쪽 빈칸을 1칸에서 K칸 움직일 수 있다. 

진영이가 시작점에서 도착점까지 이동하는 최소시간을 구해라.

 

풀이 (N*M)

• BFS

BFS로 쉽게 풀 수 있을 것 같아 보이는 문제다. 실제로도 그렇지만 신경 써야할 것이 하나 있다.

각 정점에서 1~K를 모두 보면서 업데이트 하면 O(N*M*K)로 시간초과다. 따라서 break를 써줘야 하는데 이게 좀 까다롭다. 1~K 순서대로 업데이트 하다 방문한 정점이 나왔을 때 break 해버린다면 문제가 생긴다. 해당 정점의 시간이 (현재시간+1)이고 그 다음 정점의 최적이 (현재시간+1)일 때 업데이트를 해주지 못한다. 따라서 다음 정점의 시간이 현재시간과 같은 때만 break 해주면 된다. 현재정점에서 할 수 있는 업데이트 +알파를 다음 정점에서 해줄 수 있기 때문에 최적을 구할 수 있다.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int dx[]{0,0,-1,1},dy[]{-1,1,0,0};

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n,m,k;cin>>n>>m>>k;
    vector<vector<char>> ar(n,vector<char>(m));
    for(auto&x:ar)
        for(auto&y:x)
            cin>>y;
    int sx,sy,tx,ty;cin>>sx>>sy>>tx>>ty;sx--,sy--,tx--,ty--;
    vector<vector<int>> dis(n,vector<int>(m));
    bool vis[n][m][4]{};
    queue<array<int,2>> q;
    dis[sx][sy]=1;q.push({sx,sy});
    while(q.size()) {
        auto [cx,cy]=q.front();q.pop();
        //cout<<cx<<' '<<cy<<'\n';
        for(int d=0;d<4;d++) {
            int nx=cx+dx[d],ny=cy+dy[d];    
            for(int i=0;i<k&&nx>=0&&ny>=0&&nx<n&&ny<m&&ar[nx][ny]=='.';i++) {
                if(dis[nx][ny]==dis[cx][cy])
                    break;
                if(!dis[nx][ny]) {
                    dis[nx][ny]=dis[cx][cy]+1;
                    q.push({nx,ny});
                }
                nx+=dx[d],ny+=dy[d];
            }
        }
    }
    cout<<dis[tx][ty]-1;
}