글 읽기 - 시간 초과 질문드립니다.

sagjin0000 2년 전 0

다익스트라를 이용해 구현해봤습니다.
시간 초과를 해결할 수 없어 질문드립니다....
#include <bits/stdc++.h>
#define sync() ios_base::sync_with_stdio(0); cin.tie(0)
#define endl "\n"
#define fs first
#define se second
#define pb push_back
#define popb pop_back
#define getx(x, i) get<(x)>((i))
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<vi> vvi;
typedef tuple<int, int, int> ti;
typedef tuple<ll, ll, ll> tl;
typedef vector<ti> vti;
typedef vector<tl> vtl;

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;

const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

int N, H, W, M, K;
int r[10];
int board[500][500];

// point[i][j]: (i, j)에 위치한 유닛의 번호 (0: 없음)
// act[i], team[i], pos[i]: i번 유닛의 행동력, 팀, 위치
int point[500][500];
vi act, team;
vii pos;

bool dijkstra(int u, int a, int b){
    // (sy, sz) 시작점
    // dist[i][j] : 시작점에서부터 (i, j)까지 거리
    int sy = pos[u].fs, sx = pos[u].se;
    vvi dist(H, vi(W, INF));
    priority_queue<ti> pq;

    dist[sy][sx] = 0;
    pq.push({0, sy, sx});

    while(!pq.empty()){
        int cost = -getx(0, pq.top());
        int y = getx(1, pq.top()), x = getx(2, pq.top());
        pq.pop();

        // pq에서 꺼내온 것이 기록되어있는 것보다 크면 continue
        if(dist[y][x] < cost) continue;

        // 인접한 곳에 상대편이 있다면 while문으로 continue
        // 시작점은 예외
        int flag = 0;
        for(int i = 0; i < 4; ++i){
            if(y == sy && x == sx) break;
            int ny = y + dy[i], nx = x + dx[i];

            if(ny < 0 || nx < 0 || H <= ny || W <= nx) continue;

            int p = point[nx][ny];
            if(p && team[p] != team[u]) flag = 1;
        }
        if (flag) continue;

        // 인접한 곳이 접근 불가능하면 for문 continue
        // 인접한 곳까지의 cost가 현재 기록된 것과 행동력보다 작으면
        // pq에 push 및 거리 갱신
        // * 인접한 곳이 goal이라면 true 반환
        for(int i = 0; i < 4; ++i){
            int ny = y + dy[i], nx = x + dx[i];

            if(ny < 0 || nx < 0 || H <= ny || W <= nx) continue;

            if(r[board[ny][nx]] == -1) continue;

            int ncost = cost + r[board[ny][nx]];

            if(ncost < dist[ny][nx] && ncost <= act[u]){
                if(ny == a && nx == b) return true;

                pq.push({-ncost, ny, nx});
                dist[ny][nx] = ncost;
            }
        }
        
    }

    return false;
}

void solve(int u, int a, int b){
    // dijkstra를 실행했을 때, true가 반환되면
    // 현재 점의 위치 갱신
    if(dijkstra(u, a, b)){
        pos[u] = {a, b};
        point[a][b] = u;
        point[pos[u].fs][pos[u].se] = 0;
    }
}

int main(){
    sync();
    
    cin >> N >> H >> W;
    
    for(int i = 0; i < H; ++i)
        for(int j = 0; j < W; ++j)
            cin >> board[i][j];

    for(int i = 1; i <= N; ++i)
        cin >> r[i];

    // 유닛 번호는 1부터 시작하기 때문에 M + 1개로 초기화
    cin >> M;
    act.assign(M + 1, 0);
    team.assign(M + 1, 0);
    pos.assign(M + 1, {0, 0});
    
    for(int i = 1; i <= M; ++i){
        int m, t, a, b; cin >> m >> t >> a >> b;

        act[i] = m; team[i] = t;
        pos[i] = {a, b};
        point[a][b] = i;
    }

    cin >> K;
    for(int i = 0; i < K; ++i){
        int u, a, b; cin >> u >> a >> b;
        
        // 만약 목적지에 유닛이 있거나, 접근 불가능하면 continue
        if(point[a][b] || r[board[a][b]] == -1) continue;

        solve(u, a, b);
    }

    // 1 ~ M번까지 위치 출력
    for(int i = 1; i <= M; ++i)
        cout << pos[i].fs << " " << pos[i].se << endl;

    return 0;
}
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

시간 초과 질문드립니다.

sagjin0000 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
