글 읽기 - 16367 c++ 조언을 부탁드립니다.

elvpfhhrm 1년 전 0

기존 풀이를 가지고 어찌어찌 짜 보았습니다.

다른 분들의 풀이를 참조하되 되도록 코드를 보지 않고 해보았지만 outofbounds를 받았습니다. 2-sat문제를 풀면서 outofBounds를 여러번 받았기에 어디서 틀리는 지를 확실히 알아야 할 것 같았습니다.

고수님들의 조언을 부탁드립니다. 왜 outofbounds가 뜨는 건지 코드의 어디를 고쳐야 하는건지, 제 스스로 고쳐보려 했지만 제 실력으로는 파악할 수 없었습니다.

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;

int id=0,sccid=1,N,M;
int IDS[10001],SCCIDS[10001];

vector<int> edges[10001];
vector<pii> iEdges;

stack<int> st;

pii change(int x)
{
    int notX;
    if(x<0)
    {
        notX=(-x)*2;
        x=(-x)*+1;
    }
    else
    {
        notX=x*2+1;
        x=x*2;
    }
    return {x,notX};
}

int DFS(int now)
{
    st.push(now);
    int result=IDS[now]=++id;
    
    for(int next : edges[now])
    {
        if(IDS[next]==0)result=min(result,DFS(next));
        else if(SCCIDS[next]==0)result=min(result,IDS[next]);
    }
    
    if(result==IDS[now])
    {
        int temp;
        while(1)
        {
            temp=st.top(); st.pop();
            SCCIDS[temp]=sccid;
            if(temp==now)break;
        }
        sccid++;
    }
    return result;
}

void MakeGraph()
{
    pii from,to;
    
    for(int i=0;i<M;i++)
    {
        from.first=iEdges[i].first;
        to.first=iEdges[i].second;
        
        from=change(from.first);
        to=change(to.first);
        
        edges[from.second].push_back(to.first);
        edges[to.second].push_back(from.first);//왜 여기서 outofBounds가 뜨는 걸까?
    }
}

vector<char> Solve2Sat()
{
    for(int i=2;i<=(N+1)*2;i++)
    {
        if(SCCIDS[i]==SCCIDS[i+1])return vector<char>();
    }
    
    vector<pii> sat_order;
    for(int i=2;i<=(N+1)*2;i++)
    {
        sat_order.push_back(make_pair(-SCCIDS[i],i));
    }
    
    sort(sat_order.begin(),sat_order.end());
    
    vector<char> answer(N+1);
    for(int i=0;i<sat_order.size();i++)
    {
        int vertex=sat_order[i].second;
        int var_index=vertex/2;
        char color=(vertex%2==1)?'R':'B';
        
        if(answer[var_index]!=0)continue;
        
        answer[var_index]=color;
    }
    return answer;
}

int main()
{
    cin>>N>>M;
    
    for(int i=0;i<M;i++)
    {
        int index[4];char colors[4];
        for(int j=0;j<3;j++)cin>>index[i]>>colors[i];
        
        index[3]=index[0]; colors[3]=colors[0];
        for(int j=0;j<4;j++)if(colors[i]=='B')index[i]*=-1;
        
        for(int j=0;j<3;j++)
            iEdges.push_back(make_pair(index[j],index[j+1]));
    }
    
    MakeGraph();
    
    for(int i=2;i<=N*2+1;i++)
    {
        if(IDS[i]==0)DFS(i);
    }
    
    vector<char> answer=Solve2Sat();
    
    if(answer.size()==0)cout<<-1<<'\n';
    else
    {
        for(int i=1;i<answer.size();i++)
        {
            cout<<answer[i];
        }
        cout<<'\n';
    }
    
    return 0;
}

djs100201 1년 전 0

x 랑 ~x랑 저장해야 해서 배열 크기는 20000이상이 되어야 할 듯 합니다.

elvpfhhrm 1년 전 0

문제에서 k의 최대값이 5000으로 되어있었기에 그 2배인 10000으로 한 것입니다. 다른 분들의 풀이에서도 10001~10005 정도로 되어있기에 배열크기 문제는 아닐 것 같다고 생각합니다.

jhg62002 1년 전 0

25번째 줄에 notX=x*2+1; 이부분이 x가 5000 일 때 10001이 돼서 문제가 생기는거 아닌가요??

elvpfhhrm 1년 전 0

한 달 전에 작성했던 코드라 정확히 기억이 나진 않습니다. 아래는 정답 판정을 받은 코드입니다. 다른 분들의 풀이를 참조해서 풀었던 걸로 기억합니다.

이 코드에서는 배열 크기를 10000으로 해놓아도 정답이 나오긴했습니다.

#include <bits/stdc++.h>

using namespace std;

const int Max=10004;
int id,sccid=1,N,M;
int IDS[Max],SCCIDS[Max];
vector<vector<int>> edges(Max);

stack<int> st;

int DFS(int now)
{
    st.push(now);
    //cout<<"In: "<<now<<'\n';
    
    int result=IDS[now]=++id;
    for(int next:edges[now])
    {
        if(IDS[next]==0)
        {
            //cout<<"now: "<<now<<" next: "<<next<<'\n';
            result=min(result,DFS(next));
        }
        else if(SCCIDS[next]==0)
        {
            //cout<<"already visit: "<<next<<'\n';
            result=min(result,IDS[next]);
        }
    }
    
    if(result==IDS[now])
    {
        int temp;
        while(1)
        {
            temp=st.top(); st.pop();
            SCCIDS[temp]=sccid;
            //cout<<"pop: "<<now<<" "<<temp<<" "<<sccid<<'\n';
            if(now==temp)break;
        }
        sccid++;
    }
    return result;
}

bool isPossible()
{
    bool result=true;
    for(int i=2;i<=N*2;i+=2)
    {
        if(SCCIDS[i]==SCCIDS[i+1])
        {
            //cout<<i<<" "<<i+1<<" "<<SCCIDS[i]<<" "<<SCCIDS[i+1]<<'\n';
            result=false;
            break;
        }
    }
    return result;
}

int main()
{
    cin>>N>>M;
    
    int a,b,c,not_a,not_b,not_c;
    char x,y,z;
    
    for(int i=0;i<M;i++)
    {
        cin>>a>>x>>b>>y>>c>>z;
        if(x=='R')
        {
            a=a*2;
            not_a=a+1;
        }
        else
        {
            a=a*2+1;
            not_a=a-1;
        }
        if(y=='R')
        {
            b=b*2;
            not_b=b+1;
        }
        else
        {
            b=b*2+1;
            not_b=b-1;
        }
        if(z=='R')
        {
            c=c*2;
            not_c=c+1;
        }
        else
        {
            c=c*2+1;
            not_c=c-1;
        }
        
        edges[not_a].push_back(b);
        edges[not_b].push_back(a);
        edges[not_b].push_back(c);
        edges[not_c].push_back(b);
        edges[not_c].push_back(a);
        edges[not_a].push_back(c);
    }
    
    for(int i=2;i<=N*2+1;i++)
    {
        if(IDS[i]==0)DFS(i);
    }
    
    vector<char> answer(N+1);
    if(isPossible())
    {
        vector<pair<int,int>> order;
        for(int i=2;i<=N*2+1;i++)
        {
            order.push_back(make_pair(-SCCIDS[i],i));
        }
        sort(order.begin(),order.end());
        
        for(int i=0;i<order.size();i++)
        {
            int vertex=order[i].second;
            int var_index=vertex/2;
            
            if(answer[var_index]!=0)continue;
            
            if(vertex%2==1)answer[var_index]='R';
            else answer[var_index]='B';
        }
        for(int i=1;i<answer.size();i++)
            cout<<answer[i];
        cout<<'\n';
    }
    else
    {
        cout<<"-1"<<'\n';
    }
    
    return 0;
}

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

문제

문제

출처

ICPC

16367 c++ 조언을 부탁드립니다.

elvpfhhrm 1년 전 0

djs100201 1년 전 0

elvpfhhrm 1년 전 0

jhg62002 1년 전 0

elvpfhhrm 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말