글 읽기 - 14714번 질문입니다...

steve11344 6년 전 0

우선, A라는 사람에서 시작된 찍기를 visit[0]배열에 bfs를 사용하여 최단거리를 구하였고,

마찬가지로, B라는 사람에서 시작된 찍기를 visit[1]배열에 저장하였습니다.

그 후, 두 찍기를 비교해가며, i번째 사람을 볼 때, visit[0][i]과 visit[1][i] 둘다 탐색되었어야 하고,

A에서 시작된 찍기는 B에서 찍은 횟수보다 +1이므로 하나는 홀수, 하나는 짝수여야 한다고 생각했습니다.

그때, visit[0][i] > visit[1][i]면 ans = 2*visit[0][i]-1, else , ans = 2*visit[1][i]+1을 하였고,

B에서 시작된 찍기에서 종료되었을때, ans =2*max(visit[0][i],visit[0][i])라고 생각하였습니다.

접근방법이 잘못되었나요? 아니면 어떤 예외처리를 하지 못해서 틀린걸까요?

#include <iostream>
#include <queue>
using namespace std;
int n,a,b,da,db;
int visit[2][505];
const int lala = 200000000;
queue<int> q;
int min(ll a,ll b) {return a>b?b:a;}
void bfs(int x, int dx, int flag){
    q.push(x);
    visit[flag][x] = 0;
    int tmp = 0;
    while(!q.empty()){
        tmp = q.front();
        q.pop();
        int left = tmp-dx<=0?n+(tmp-dx):tmp-dx;
        int right = tmp+dx>n?(tmp+dx)%n:tmp+dx;
        if(visit[flag][left]>visit[flag][tmp]+1) visit[flag][left] = visit[flag][tmp]+1,q.push(left);
        if(visit[flag][right]>visit[flag][tmp]+1) visit[flag][right] = visit[flag][tmp]+1,q.push(right);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> a >> b >> da >> db;
    for(int i = 0 ; i<=504; i++) visit[0][i] = visit[1][i] = lala;
    bfs(a,da,0);
    bfs(b,db,1);
    int ans =lala,tmp=0;
    for(int i =1 ; i<=n ;i++){
        if(visit[0][i] != lala && visit[1][i] != lala){
            if(visit[0][i]%2 !=visit[1][i]%2){
                if(visit[0][i] > visit[1][i]) tmp = (2*visit[0][i])-1;
                else tmp = (2*visit[1][i])+1;
            }else{
                if(visit[0][i] > visit[1][i]) tmp = visit[0][i]*2;
                else tmp = visit[1][i]*2;
            }
            ans = min(ans,tmp);
        }
    }
    if(ans == lala) cout << "Evil Galazy" << endl;
    else cout << ans << endl;
    return 0;
}

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

문제

문제

출처

ICPC

14714번 질문입니다...

steve11344 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말