글 읽기 - [c++] 1953 팀배분 bfs로 푸는데 틀렸습니다

dnjs1318 2년 전 0

아래처럼 풀었는데 틀렸습니다가 나오더라고요

만약에 싸이클(아래처럼)이 생긴다면 큐에 먼저들어오는 2와 4의 색은 둘다 흰색이 맞는걸까요 아니면 2는 흰색 4는 파란색이 맞는건가요?

3(파랑)

2(흰색) 4(?)

아무거나 되어도 상관없는건가요?

그리고 반례도 찾아주시면 감사하겠습니다 ㅜㅜ

#include <bits/stdc++.h>

using namespace std;

int N;
bool connect[101][101];
bool visit[101];
int color_map[101]; // blue = 1, white = 0, else = -1;

vector<int > blue;
vector<int> white;

void BFS(int x)
{
    queue <int> q;
    q.push(x);
    while(!q.empty())
    {
        int first = q.front();
        visit[first] = true;
        q.pop();

        for(int i=1; i<=N; i++)
        {
            if (connect[first][i] && !visit[i])
            {
                q.push(i);
                visit[i] = true;
                if (color_map[first] == -1) //색 지정 없이 처음 들어온 경우 파란색으로 설정
                {
                    color_map[first] = 1;
                    blue.push_back(first);
                }
                if (color_map[first] == 1)
                {
                    white.push_back(i);
                    color_map[i] = 0;
                }
                else if (color_map[first] == 0)
                {    
                    color_map[i] = 1;
                    blue.push_back(i);
                } 
                
            }
           
        }
    }
}


void isConcentrated()
{
    if (white.size() == 0)
    {
        int temp = blue[blue.size()-1];
        blue.pop_back();
        white.push_back(temp);
    }
    if (blue.size() == 0)
    {
        int temp = white[white.size()-1];
        white.pop_back();
        blue.push_back(temp);
    }
}


int main()
{
    //  N은 학생수 
    scanf("%d", &N);

    memset(visit, false, sizeof(visit));
    memset(connect, false, sizeof(connect));
    memset(color_map, -1, sizeof(color_map));

    //  input
    for(int i=1; i<=N; i++)
    {
        int a;
        scanf("%d", &a);
        for(int j=0; j<a; j++)
        {
            int b;
            scanf("%d", &b);
            connect[i][b] = true;
            connect[b][i] = true;
        }
    }

    for(int i=1; i<=N; i++)
    {
        if(!visit[i])
        {
            BFS(i);
        }
    }
    isConcentrated();
    sort(blue.begin(), blue.end());
    sort(white.begin(), white.end());
    printf("%lu\n", bsize);
    for(int i = 0; i<blue.size();i++)
    {
        printf("%d ", blue[i]);
    }
    printf("\n%lu\n", wsize);
    for(int i = 0; i<white.size();i++)
    {
        printf("%d ", white[i]);
    }


}   // 두 집합에 하나는 무조건 있어야함


/*
6
1 5
2 5 3
2 2 6
1 6
2 2 4
2 4 3
______
3
1 2 4 
3
3 5 6 


7
2 7 6
1 3
1 5
2 3 2
2 4 7
1 7
1 5
_____
3
1 2 5 
4
3 4 6 7 

*/

dnjs1318 2년 전 0

인 경우를 처리를 안 해줘서 틀렸던 것 같습니다.

그거랑 다른거 좀 더 고쳐서 냈더니 맞았습니다.

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

문제

문제

출처

ICPC

[c++] 1953 팀배분 bfs로 푸는데 틀렸습니다

dnjs1318 2년 전 0

dnjs1318 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말