글 읽기 - 둘이 비슷한 로직 같은데 값이 다르게 나오는 이유가 무엇인지 궁금합니다.

hello70825 4년 전 0

비트마스크 + BFS로 풀었습니다.

첫 번째 코드는 통과 코드이고, 두 번째 코드는 예제 값부터 다르게 나오는 코드입니다.

제가 보기엔 둘의 결과가 똑같을 것 같은데, 왜 두번째 코드에 예제를 입력하면 답이랑 다르게 0번 섬에서 돌을 줍지 않는 것이 최댓값이라고 나오는지 궁금합니다.

#include <bits/stdc++.h>
using namespace std;

int n,m,k;
int Land[101];
int D[101][101];
int check[16384][101];
queue<pair<int,int>> q;
pair<int,int>p;


int main(){
    memset(Land,-1,sizeof(Land)); //보석이 있는 섬이면 0이상의 값, 없으면 -1
    memset(D,-1,sizeof(D)); // 다리
    memset(check,-1,sizeof(check)); // 지금 좌표에서 가질 수 있는 최대 보석의 수
    cin >> n >> m >> k;
    int ans = 0;
    for(int i = 0; i < k; i++) {
        int z;
        cin >> z;
        Land[z-1] = i;
    }
    for(int i = 0; i < m; i++){
        int a,b,c;
        cin >> a >> b >> c;
        D[a-1][b-1]=c;
        D[b-1][a-1]=c;
    }
    check[0][0]=0;
    q.push(make_pair(0,0));
    while(!q.empty()){
        p = q.front();q.pop();
        int key = p.first; //보석을 주운 섬의 번호들
        int x = p.second; // 현재 위치
        if(x==0) ans=max(check[key][x],ans); // 0번 섬에 왔으면 ans 최대값을 갱신함
        if(Land[x]!=-1 && !(key & 1<<Land[x])){ //x섬에 보석이 있는데 그동안 줍지 않았을 경우
            int nkey = key | 1<<Land[x];
            if(check[nkey][x]<check[key][x]+1){
                check[nkey][x]=check[key][x]+1;
                q.push(make_pair(nkey, x));
            }
        }
        for(int i = 0; i < n; i++){ // for문을 이용해 x번 섬에서 nx번 섬으로 이동할 곳이 있는지 확인
            int nx = i;
            int Max = D[x][i];
            if(check[key][x]<=Max && check[key][nx]<check[key][x]){
                check[key][nx]=check[key][x];
                q.push(make_pair(key,nx));
            }
        }
    }
    cout << ans << endl;
}




----------------------------------------------------------------------------------------
    
    
#include <bits/stdc++.h>
using namespace std;

int n,m,k;
int Land[101];
int D[101][1001];
int check[16384][101];
queue<pair<int,int>> q;
pair<int,int>p;


int main(){
    memset(Land,-1,sizeof(Land));
    memset(D,-1,sizeof(D));
    memset(check,-1,sizeof(check));
    cin >> n >> m >> k;
    int ans = 0;
    for(int i = 0; i < k; i++) {
        int z;
        cin >> z;
        Land[z-1] = i;
    }
    for(int i = 0; i < m; i++){
        int a,b,c;
        cin >> a >> b >> c;
        D[a-1][b-1]=c;
        D[b-1][a-1]=c;
    }
    if(Land[0]!=-1){
        check[1<<Land[0]][0]=1;
        q.push(make_pair(1<<Land[0],0));
    }
    check[0][0]=0;
    q.push(make_pair(0,0));
    while(!q.empty()){
        p = q.front();q.pop();
        int key = p.first;
        int x = p.second;
        if(x==0) if(check[key][x]>ans){
            ans=check[key][x];
            cout<<key<<endl;
        }
        for(int i = 0; i < n; i++){
            int nx = i;
            int Max = D[x][nx];
            if(check[key][x]+1<=Max && Land[nx]!=-1 && !(key & 1<<Land[nx])){
                int nkey = key | 1<<Land[nx]; //nx번 섬에 보석이 있을 경우 줍는 경우
                if(check[nkey][nx]<check[key][x]+1){
                    check[nkey][nx]=check[key][x]+1;
                    q.push(make_pair(nkey, nx));
                }
            }
            if(check[key][x]<=Max && check[key][nx]<check[key][x]){
                check[key][nx]=check[key][x]; //nx번 섬에 보석이 있든 말든 줍지 않는 경우
                q.push(make_pair(key,nx));
            }
        }
    }
    cout << ans << endl;
}

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

문제

문제

출처

ICPC

둘이 비슷한 로직 같은데 값이 다르게 나오는 이유가 무엇인지 궁금합니다.

hello70825 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말