[16930] 달리기

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

16930번: 달리기

<문제>

간단하게 생각하면 4NMK정도의 풀이를 떠올릴 수 있는데, N, M, K모두 1'000이라 불가능하다.

그래서 O(NMK)를 O(NM)정도로 줄여야하는데, 핵심은 방문처리를 bool이 아닌 int형으로 해주는것이다.

코드 자체는 얼핏보기에 O(NMK)인데, 32번라인의

if (vst[y][x] < vst[cur.y][cur.x] + 1) break;

위 한줄이 큰 역할을 맡아준다. 

더불어, 먼저 도착하는것이 최적해라는 일반성은 잃지 않았으므로 (ey, ex)에 도착하면 바로 리턴할 수 있다.

 

어찌보면 당연한 이야기지만,

y=cur.y+dy[i]*rep;

x=cur.x+dx[i]*rep;

 

위 두 문장에서 rep의 범위는  [1, k]가 되어야 하므로 while()이 아니라 for()가 조금 더 직관적이고 간단하다.

초기에는 while(1)로 구현을 하고, 적절히 분기하려고 시도했는데, 이러면 더 복잡하다..

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n, m, k, sy, sx, ey, ex;
int dy[4] = {0, 1, 0, -1}, dx[4] = {1, 0, -1, 0};
char a[1003][1003];
int vst[1003][1003];
typedef struct {
    int y, x;
} state;
bool isValid(int y, int x) {
    return (y >= 0 && x >= 0 && y < n && x < m && a[y][x] != '#');
}
int f(void) {
    queue<state> q;
    q.push({sy, sx});
    vst[sy][sx] = 0;
    while (!q.empty()) {
        state cur = q.front();
        q.pop();
        if (vst[ey][ex] != -1) return vst[ey][ex];
        for (int i = 0; i < 4; i++) {
            int y = cur.y;
            int x = cur.x;
            for (int j = 0; j < k; j++) {
                y += dy[i];
                x += dx[i];
                if (isValid(y, x) == false) break;
                if (vst[y][x] == -1) {
                    q.push({y, x});
                    vst[y][x] = vst[cur.y][cur.x] + 1;
                }
                if (vst[y][x] < vst[cur.y][cur.x] + 1) break;
            }
        }
    }
    if (vst[ey][ex] == -1) return -1;
    return vst[ey][ex];
}
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> k;
    int i, j;
    for (i = 0; i < n; i++)
        for (j = 0; j < m; j++) cin >> a[i][j];
    cin >> sy >> sx >> ey >> ex;
    sy--;
    sx--;
    ey--;
    ex--;
    memset(vst, -1, sizeof(vst));
    cout << f();
    return 0;
}