16930번 달리기

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

백준 boj 16930 bfs 시간초과 queue push 아이디어 생각

재채점 후 시간 초과가 발생했다.

계속 시간 초과가 발생하길래 다른 분의 코드에서 힌트를 얻어서 구현봤다.

최대한 덜 queue에 push하려고 했었지만, 다시는 푼 시간 초과 코드에서 결국 줄이지 못 했던 것 같다.

핵심은 T[y][x]가 INF일 때만 queue에 push하는 것이다. 즉, 아직 방문하지 않은 곳만을 탐색하는 것이다.

물론 그 전에 T[y][x]가 T[r][c] + 1보다 이상이어야 한다.

T[y][x] < T[r][c] + 1일 때는 break해야 한다. 이미 최소 시간이 보장된 길인데, 굳이 탐색할 필요가 없다.

제일 처음 풀었을 당시 맞았던 코드이지만, 재채점 이후 시간 초과가 뜨는 코드

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
#include <set>
#include <tuple>
 
#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")
 
using namespace std;
 
// https://www.acmicpc.net/problem/16930
 
char Map[1010][1010];
 
bool visit[1010][1010] = { false, };
 
queue<pair<int, int> > q;
 
int N = 0, M = 0, K = 0, sy = 0, sx = 0, ey = 0, ex = 0;
 
int BFS()
{
    q.push({ sy, sx });
 
    visit[sy][sx] = true;
 
    int ret = 0;
 
    while (!q.empty())
    {
        int qSize = q.size();
 
        while (qSize--)
        {
            int r = q.front().first;
            int c = q.front().second;
 
            q.pop();
 
            if (r == ey && c == ex) return ret;
            
            for (int i = 0; i < 4; i++)
            {
                int y = r, x = c, move = 1, temp = 0;
 
                while (temp < K)
                {
                    if (i == 0) x += move;
                    else if (i == 1) y += move;
                    else if (i == 2) x -= move;
                    else if (i == 3) y -= move;
 
                    // if (y < 0 || y >= N || x < 0 || x >= M || Map[y][x] == '#' || visit[y][x] ) break;
                    // 처음에 위에 처럼 썼었다.(가는 길 중간 칸이 방문되었던 곳이면 바로 break로 구현했었음.
                    // 즉, 가는 중간 칸을 방문했다고 해서, 
                    // 그 다음 칸을 (방문하지 않았는데도 불구하고) 못 가는 것은 아니다.
                    // [출발][1][2][3][4] : [2]만 방문했다고 했을 때, [3], [4]도 갈 수는 있다. 
 
                    if (y < 0 || y >= N || x < 0 || x >= M || Map[y][x] == '#' ) break;
 
                    if (!visit[y][x])
                    {
                        q.push({ y, x });
                        visit[y][x] = true;
                    }
 
                    ++temp;
                }
            }
        }
 
        ++ret;
    }
 
    return -1;
}
 
int main(void)
{
    scanf("%d %d %d", &N, &M, &K);
 
    for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) cin >> Map[i][j];
 
    scanf("%d %d %d %d", &sy, &sx, &ey, &ex);
 
    --sy; --sx; --ey; --ex;
 
    printf("%d\n", BFS());
 
    return 0;
}

다시 풀어봤지만 또 시간 초과가 뜬 코드 2개

#include <bits/stdc++.h>
 
using namespace std;
 
#define Max 1001
#define INF 2e9
 
typedef struct info
{
    int y, x, d, len;
}info;
 
int R, C, K, sy, sx, ey, ex;
int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { 1, 0, -1, 0 };
char m[Max][Max];
queue<info> q;
int T[Max][Max];
 
int bfs()
{
    int ret = INT32_MAX;
 
    for (int i = 0; i < 4; i++) {
        q.push({ sy, sx, i, 1});
        T[sy][sx] = 0;
    }
 
    while (!q.empty())
    {
        int dqs = q.size();
 
        while (dqs--)
        {
            int r = q.front().y;
            int c = q.front().x;
            int d = q.front().d;
            int len = q.front().len;
 
            // printf("(%d, %d), len = %d, d = %d, 시간 = %d\n\n", r, c, len, d, T[r][c]);
 
            q.pop();
 
            for (int i = 0; i < 4; i++) {
                int y = r + dy[i];
                int x = c + dx[i];
                int Time = T[r][c];
                int L = len;
 
                if (y < 0 || y >= R || x < 0 || x >= C || m[y][x] == '#') {
                    continue;
                }
 
                if (i != d || len + 1 >= K) {
                    ++Time;
                    L = 0;
                }
                else {
                    ++L;
                }
 
                if (T[y][x] >= Time) {
                    T[y][x] = Time;
                    q.push({ y, x, i, L });
                }
            }
        }
    }
 
    return T[ey][ex] == INF ? -1 : T[ey][ex];
}
 
int main()
{
    cin.tie(0);
    cin >> R >> C >> K;
 
    for (int i = 0; i < R; i++) {
        scanf("%s", &m[i][0]);
        for (int j = 0; j < C; j++) {
            T[i][j] = INF;
        }
    }
 
    cin >> sy >> sx >> ey >> ex;
 
    --sy; --sx; --ey; --ex;
 
    int g = bfs();
 
    if (g == -1) {
        printf("-1\n");
        return 0;
    }
 
    printf("%d\n", g);
 
    return 0;
}

#include <bits/stdc++.h>
 
using namespace std;
 
#define Max 1001
#define INF 2e9
 
typedef struct info
{
    int y, x, d, len;
}info;
 
int R, C, K, sy, sx, ey, ex;
int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { 1, 0, -1, 0 };
char m[Max][Max];
queue<info> q;
int T[Max][Max];
 
int bfs()
{
    int ret = INT32_MAX;
    bool isArrive = false;
 
    for (int i = 0; i < 4; i++) {
        q.push({ sy, sx, i, 0});
        T[sy][sx] = 0;
    }
 
    while (!q.empty())
    {
        int dqs = q.size();
 
        while (dqs--)
        {
            int r = q.front().y;
            int c = q.front().x;
            int d = q.front().d;
            int len = q.front().len;
 
            //printf("T[%d][%d] = %d, d = %d\n", r, c, T[r][c], d);
 
            q.pop();
 
            for (int i = 0; i < 4; i++) {
                int y = r + dy[i];
                int x = c + dx[i];
 
                if (y < 0 || y >= R || x < 0 || x >= C || m[y][x] == '#') {
                    continue;
                }
                
                if (i == d && len + 1 < K) {
                    if (T[y][x] >= T[r][c]) {
                        //printf("len = %d, y = %d, x = %d\n", len, y, x);
                        //printf("test\n");
                        T[y][x] = T[r][c];
                        if (r == 0 && c == 0) {
                            ++T[y][x];
                        }
                        q.push({ y, x, i, len + 1 });
                    }
                }
                else {
                    if (T[y][x] >= T[r][c] + 1) {
                        //printf("T[%d][%d](%d) >= T[%d][%d](%d) + 1\n", y, x, T[y][x], r, c, T[r][c]);
                        //printf("i = %d, d = %d\n", i, d);
                        T[y][x] = T[r][c] + 1;
                        q.push({ y, x, i, 0 });
                    }
                }
            }
        }
    }
 
    return T[ey][ex] == INF ? -1 : T[ey][ex];
}
 
int main()
{
    cin.tie(0);
    cin >> R >> C >> K;
 
    for (int i = 0; i < R; i++) {
        scanf("%s", &m[i][0]);
        for (int j = 0; j < C; j++) {
            T[i][j] = INF;
        }
    }
 
    cin >> sy >> sx >> ey >> ex;
 
    --sy; --sx; --ey; --ex;
 
    int g = bfs();
 
    if (g == -1) {
        printf("-1\n");
        return 0;
    }
 
    printf("%d\n", g);
 
    return 0;
}

정답 코드

#include <bits/stdc++.h>
 
using namespace std;
 
#define Max 1001
#define INF 2e9
 
int R, C, K, sy, sx, ey, ex;
int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { 1, 0, -1, 0 };
char m[Max][Max];
queue<pair<int, int> > q;
int T[Max][Max];
 
int bfs()
{
    int ret = INT32_MAX;
 
    q.push({ sy, sx });
    T[sy][sx] = 0;
 
    while (!q.empty())
    {
        int qs = q.size();
 
        while (qs--)
        {
            int r = q.front().first;
            int c = q.front().second;
 
            q.pop();
 
            for (int i = 0; i < 4; i++) {
                for (int k = 1; k <= K; k++) {
                    int y = r + dy[i] * k;
                    int x = c + dx[i] * k;
 
                    // T[y][x] == T[r][c] + 1; 일 때도 탐색을 해야 한다.
                    // 즉, <=가 아니라 <이다.
                    if (y < 0 || y >= R || x < 0 || x >= C || m[y][x] == '#' || T[y][x] < T[r][c] + 1) {
                        break;
                    }
            
                    // if 문 없으면, 시간 초과 발생(q에 많이 push 되는 듯)
                    // if 문의 의도는 방문하지 않은 곳만을 최우선적으로 탐색
                    if (T[y][x] == INF) {
                        T[y][x] = T[r][c] + 1;
                        q.push({ y, x });
                    }
                }
            }
        }
    }
 
    return T[ey][ex] == INF ? -1 : T[ey][ex];
}
 
int main()
{
    cin.tie(0);
    cin >> R >> C >> K;
 
    for (int i = 0; i < R; i++) {
        scanf("%s", &m[i][0]);
        for (int j = 0; j < C; j++) {
            T[i][j] = INF;
        }
    }
 
    cin >> sy >> sx >> ey >> ex;
 
    --sy; --sx; --ey; --ex;
 
    int g = bfs();
 
    if (g == -1) {
        printf("-1\n");
        return 0;
    }
 
    printf("%d\n", g);
 
    return 0;
}