글 읽기 - 접근방법이 틀린 건가요??

yhc3006 4년 전 0

안녕하세요. 회로배치 문제 질문 올립니다.

시작점 A에서 끝점 B를 연결하기 위한 최소 비용을 구하는 문제여서 우선순위 큐를 사용하여 비용이 적은 순으로 탐색을 진행하는 식으로 문제에 접근했습니다.

그런데, WA가 계속 나와서 접근 자체가 틀린 건지 아니면 반례가 있는 지 여쭤보고 싶습니다.

코드는 아래와 같습니다. 기존에는 우선순위큐에서 끝점이 나오면 바로 return 하게 구현했었는데 아예 정확하게 해보려고 해당 좌표의 최소값을 갱신하는 방식으로 변경하였습니다.

#include <iostream>
#include <queue>
#include <vector>

using namespace std;
#define MAXN 51
#define INF 987654321

bool map[MAXN][MAXN];

struct node{
    int x;
    int y;
    int dist;
    int dir;
    vector<pair<int,int> > path;

    bool operator < (const node& a) const{
        return a.dist < dist;
    }
};
node visited[MAXN][MAXN];
priority_queue<node> pq;
int N,M,K;
int sx1,sy1,sx2,sy2;
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
// (x1,y1) -> (x2,y2)로 가기 위한 방향 체크
int find_dir(int x1, int y1, int x2, int y2){
    if (x2 - x1 > 0 ) return 1;
    else if (x2 - x1 < 0) return 3;
    else if (y2 - y1 > 0) return 0;
    return 2;
}


void bfs(){
    vector<pair<int,int> > v;
    v.push_back({sx1,sy1});
    pq.push({sx1,sy1,0,-1,v});
    visited[sx1][sy1].dist = 0;
    while (!pq.empty()){
        int x = pq.top().x;
        int y = pq.top().y;
        int dist = pq.top().dist;
        int dir = pq.top().dir;
        vector<pair<int,int> > path = pq.top().path;
        pq.pop();
        if (x == sx2 && y == sy2){
            continue;
        }
        for (int k =0 ;k<4; k++){
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (nx <= 0|| ny<=0 || nx> N || ny > N) continue;
            int next_dist;
            if (map[nx][ny]) next_dist = dist+K;
            else next_dist = dist+1;
            if (visited[nx][ny].dist > next_dist){
                if (dir != -1 && dir != k){
                    path.push_back({x,y});
                }
                visited[nx][ny] = {nx,ny,next_dist,k,path};
                pq.push({nx,ny,next_dist,k,path});
            }
        }
    }
    
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N;
    for (int i = 1; i <= N; i++){
        for (int j = 1; j<=N; j++){
            visited[i][j].dist = INF;
        }
    }
    cin >> sx1 >> sy1 >> sx2 >> sy2;
    cin >> K >> M;
    int x,y;
    while (M--){
        int num;
        cin >> num >> x >> y;
        for (int i = 0; i< num-1; i++){
            int nx,ny;
            cin >> nx >> ny;
            int d = find_dir(x,y,nx,ny);
            while (x != nx || y != ny){
                map[x][y] = true;
                x += dx[d];
                y += dy[d];
            }
            map[x][y] = true;
        }
    }
    bfs();
    node ans = visited[sx2][sy2];
    cout << ans.dist+1 <<"\n";
    ans.path.push_back({sx2,sy2});
    cout << ans.path.size() <<" ";
    for (int i =0 ; i < ans.path.size(); i++){
        cout << ans.path[i].first <<" "<< ans.path[i].second <<" ";
    }
    return 0;
}

sait2000 4년 전 1

이걸 넣어보시죠

yhc3006 4년 전 0

와.. 이런 치명적인 실수를 했군요.. 4개의 방향에 path가 누적된 것을 만약 추가될 시 도로 pop_back 해주는 방식으로 해결하였습니다. 감사합니다!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

접근방법이 틀린 건가요??

yhc3006 4년 전 0

sait2000 4년 전 1

yhc3006 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말