글 읽기 - 왜틀렸을까요...

juwonhyme 1년 전 0

간단하게 BFS 돌리고

경로 출력하는 코드인데

왜틀렸는지...

#include<stdio.h>
#include<math.h>
#include<vector>
#include<queue>
#include<stack>
using namespace std;

vector<int> v[1010];
int A,B;

void bfs(int start)
{
    queue< pair<int,int> > q;
    int chk[1010] = {0,}; // 경로 길이
    int bt[1010] = {0,};
    q.push(make_pair(start,1));
    chk[start] = 1;
    while(!q.empty())
    {
        int cur = q.front().first;
        int num = q.front().second;
        q.pop();

        if(cur == B){
            stack<int> s;
            while(cur)
            {
                s.push(cur);
                if(cur==A)break;
                cur = bt[cur];
            }
            while(!s.empty()){
                printf("%d ",s.top());
                s.pop();
            }
            return;
        }

        for(int i=0;i<v[cur].size();i++){
            if(chk[v[cur][i]]==0 || chk[v[cur][i]] > num + 1){
                q.push(make_pair(v[cur][i],num+1));
                chk[v[cur][i]] = num+1;
                bt[v[cur][i]] = cur;
            }
        }
    }
}

int main()
{
    int N,K;
    long long int arr[1010] = {0,};
    scanf("%d %d",&N,&K);
    for(int i=1;i<=N;i++){
        long long int p = 1;
        for(int j=0;j<K-1;j++){
            p*=2;
        }
        for(int j=0;j<K;j++){
            int temp;
            scanf("%1d",&temp);
            arr[i] += temp*p;
            p/=2;
        }
    }
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            if(i==j) continue;
            if((arr[i]^arr[j])==0) continue;
            if(((long long int)1 << 30) % (arr[i]^arr[j]) == 0){
                v[i].push_back(j);
            }
        }
    }
    scanf("%d %d",&A,&B);
    bfs(A);
}

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

문제

문제

출처

ICPC

왜틀렸을까요...

juwonhyme 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말