algospot.com :: 질문과 답변: BRAVE 문제 질문있습니다.

BRAVE 문제 질문있습니다.

1

~~~ c++
#include
#include
#include

//#define CHECK

#ifdef CHECK
#include "windows.h"
#endif

using namespace std;

typedef set SSet;

typedef struct SNode_
{
SNode_()
{
}

SNode_ (int x_, int y_) 
: x(x_), y(y_)
{
}

bool Find(SNode_ const& data)
{
    if (data.x == x || data.x == y || data.y == x || data.y == y)
        return true;

    return false;
}

void InsertData(SSet& sum)
{
    sum.insert(x);
    sum.insert(y);
}

int x;
int y;

} SNode;

typedef vector SVector;
typedef vector SResult;

int Recursive(SNode& node, SVector& data, int index, SSet& sum)
{
for (int i = index + 1; i < data.size(); ++i)
{
if (node.Find(data[i]))
{
node.InsertData(sum);
data[i].InsertData(sum);

        Recursive (data[i], data, i, sum);
    }
}

return 0;

}

int Execute(int n, int m, SVector& data)
{

int maxSum = 0;

for (int i=0; i < m; ++i)
{
    SSet sum;
    Recursive(data[i], data, i, sum);

    if (sum.size() > maxSum)
    {
        maxSum = sum.size();
    }
}

return maxSum;

}

int main()
{
int testCase;
int n, m;
int x, y;
SResult re;

cin >> testCase;
re.resize(testCase);

#ifdef CHECK

int a = GetTickCount();

#endif

for (int i = 0; i < testCase; ++i)
{
    SVector data;
    cin >> n;
    cin >> m;
    data.resize(m);

    for (int j = 0; j < m; ++j)
    {
        cin >> x;
        cin >> y;
        data[j] = SNode(x, y);
    }

    re[i] = Execute(n, m, data);
}


for (int j = 0; j < re.size(); ++j)
{
    cout << re[j] << endl;
}

#ifdef CHECK

cout << "---" << GetTickCount() - a;

#endif

return 0;

}
~~~

2

~~~ c++
#include
#include

using namespace std;

char graph[10001][10001] = {{0,},};
char visited[10001][10001] = {{0,},};

int BFS(int x, int y, int n)
{
int maxSize = 0;

visited[x][y] = 1;

queue<int> q;
q.push(x);
q.push(y);
maxSize +=2;

int v = x;

while (1)
{
    for (int i=1; i<=n; ++i)
    {
        if (graph[v][i] && !visited[v][i])
        {
            q.push(i);
            visited[v][i] = 1;
            ++maxSize;
        }
        if (graph[i][v] && !visited[i][v])
        {
            q.push(i);
            visited[i][v] = 1;
            ++maxSize;
        }
    }
    q.pop();
    if (q.empty())
        break;  

    v = q.front();
}

return maxSize;

}

int main()
{
int testCase;
int n, m;
int x, y;
cin >> testCase;

for(int i=0; i<testCase; ++i)
{
    cin >> n;
    cin >> m;

    for (int j=0; j<m; ++j)
    {
        cin >> x;
        cin >> y;
        graph[x][y] = 1;
    }
    cout << BFS(x, y, n) << endl;
}

return 0;

}
~~~

3

~~~ c++
#include
#include
#include
#include

using namespace std;

struct SNode
{
SNode(int x_, int y_)
: x(x_), y(y_)
{
v = 0;

}
int x, y;
bool v;

};

typedef list LIST;

int BFS(LIST& graph, LIST::iterator& it)
{
int maxSize = 0;

queue<int> q;
q.push((*it).x);
q.push((*it).y);
maxSize +=2;

int v = (*it).x;
(*it).v = 1;

while (1)
{
    LIST::iterator it = graph.begin();

    for (; it != graph.end(); ++it)
    {
        if ((*it).x == v && (*it).v == 0)
        {
            q.push((*it).y);
            (*it).v = 1;
            ++maxSize;
        }
        if ((*it).y == v && (*it).v == 0)
        {
            q.push((*it).x);
            (*it).v = 1;
            ++maxSize;
        }
    }
    q.pop();
    if (q.empty())
    {   
        break;
    }

    v = q.front();
}

return maxSize;

}

int main()
{
int testCase;
int n, m;
int x, y;
LIST graph;

cin >> testCase;


for(int i=0; i<testCase; ++i)
{
    cin >> n;
    cin >> m;   

    for (int j=0; j<m; ++j)
    {
        cin >> x;
        cin >> y;
        graph.push_back(SNode(x, y));
    }

    int maxSize = 0;
    int cnt = 0;

    LIST::iterator it = graph.begin();
    for (; it != graph.end(); ++it)
    {
        ++cnt;
        int size = BFS(graph, it);
        if (maxSize < size)
        {
            maxSize = size;
            if (maxSize > (m - cnt) * 2)
                break;
        }
    }

    cout << maxSize << endl;

}

return 0;

}
~~~

4

~~~ c++
#include
#include

using namespace std;

struct SNode
{
SNode(int x_, int y_)
: x(x_), y(y_)
{
}
int x, y;
};

typedef list LIST;

int BFS(LIST& graph, int m)
{
LIST::iterator it = graph.begin();
int v = (*it).x;

int maxSize = 2;
int cnt = 0;

while (1)
{
    int size = 2;
    LIST::iterator it = graph.begin();

    do 
    {
        if (((*it).x == v || (*it).y == v))
        {
            if (it != graph.begin())
            {
                graph.erase(it++);
            }
            else
            {
                ++it;
            }

            ++size;

        }
        else
        {
            ++it;
        }

    } while(it != graph.end());


    graph.erase(graph.begin());

    if (maxSize < size) 
        maxSize = size;

    if (graph.empty())  
        break;

    ++cnt;

    if (maxSize > (m - cnt) * 2) 
        break;

    v = (*graph.begin()).x;
}

return maxSize;

}

int main()
{
int testCase;
int n, m;
int x, y;
LIST graph;

cin >> testCase;


for(int i=0; i<testCase; ++i)
{
    cin >> n;
    cin >> m;   

    for (int j=0; j<m; ++j)
    {
        cin >> x;
        cin >> y;
        graph.push_back(SNode(x, y));
    }

    cout << BFS(graph, m) << endl;
}

return 0;

}
~~~

5

~~~ c++
#include
#include

using namespace std;

int graph[100001][2] = {{0,},};
int queue[100001][2] = {{0,},};

char visited[100000] = {0,};

int BFS(int m)
{
int f = 0, r = 0;

queue[f][0] = graph[0][0];
queue[f][1] = graph[0][1];
visited[f] = 1;


int maxSize = 2;    
int size = 2;
int nextPos = 0, oldPos = 0;


while (1)
{

    for (int i = nextPos; i<m; ++i)
    {
        if (!visited[i])
        {
            if (nextPos == oldPos)
            {
                nextPos = i;
            }

            if (queue[f][0] == graph[i][1] || queue[f][0] == graph[i][0] || queue[f][1] == graph[i][1] || queue[f][1] == graph[i][0])
            {
                ++r;
                ++size;
                visited[i] = 1;
                queue[r][0] = graph[i][0];
                queue[r][1] = graph[i][1];
            }
        }   
    }

    ++f;

    if (f > r)
    {
        if (maxSize < size) 
             maxSize = size;

        if (maxSize >= (m - nextPos) *2)
            break;

        if (f == m)
            break;

        if (nextPos != oldPos)
        {
            queue[f][0] = graph[nextPos][0];
            queue[f][1] = graph[nextPos][1];
            visited[nextPos] = 1;
            size = 2;
            oldPos  = nextPos;
        }
        else
            break;
    }
}
return maxSize;

}

int main()
{
int testCase;
int n, m;
int x, y;
cin >> testCase;

for(int i=0; i<testCase; ++i)
{
    cin >> n;
    cin >> m;

    for (int j=0; j<m; ++j)
    {
        cin >> x;
        cin >> y;
        graph[j][0] = x;
        graph[j][1] = y;
    }

    cout << BFS(m) << endl;
}

return 0;

}

</spoiler>

-----------------------------------------------------------------
6
<spoiler>
~~~ c++

#include <iostream>
#include <algorithm>
#include <stdio.h>

using namespace std;

int graph[100001][2] = {{0,},};
int queue[100001][2] = {{0,},};

char visited[100000] = {0,};


void Insert(int& r, int index)
{
    queue[r][0] = graph[index][0];
    queue[r][1] = graph[index][1];
    ++r;
    visited[index] = 1;
}



int BFS(int m)
{
    int f = 0, r = 0;

    int maxSize = 2;    

    Insert(r, 0);

    do
    {
        int size = 2;

        for (int j=f; j<r; ++j)
        {
            
            for (int i=0; i<m; ++i)
            {
                if (!visited[i])
                {
                    if (queue[j][0] == graph[i][1] || queue[j][0] == graph[i][0] || queue[j][1] == graph[i][1] || queue[j][1] == graph[i][0])
                    {
                        Insert(r, i);       
                        ++size;
                    }
                }   
            }
        }

        f = r;  
        Insert(r, f);       

        if (maxSize < size) 
            maxSize = size;

    } while(r < m);

    return maxSize;
}

int main()
{
    int testCase;
    int n, m;
    int x, y;

    scanf("%d", &testCase);

    
    for(int i=0; i<testCase; ++i)
    {
        scanf("%d", &n);
        scanf("%d", &m);

        for (int j=0; j<m; ++j)
        {
            cin >> x;
            cin >> y;
            graph[j][0] = x;
            graph[j][1] = y;
        }
        printf("%d\n", BFS(m));
     
    }

    return 0;
}

원래 첫번째 소스대로 재귀적으로 매칭되는 데이터를 찾아가는 방
식을 쓰다가 계속 시간초과가 나서 두번째 소스로 변경했습니다.
배열로 했었고, queue도 있는 형태로 작성하다가 배열로 하면
메모리 초과, queue를 대입하는 시간조차 부족해서 시간초과..

그래서 list를 이용해서 visit 했던 노드는 삭제하는 방식으로
최종적으로 4번 소스같이 변경했는데도 여전히 시간 초과네요.
혹시 이거 푸신 분들은 어떤 식으로 푸셨나요?
제가 개념 자체를 잘못 이해하고 있는 걸까요? ㅠ

11년 전

11개의 댓글이 있습니다.

Being

아래 코드를 BFS라고 적어 두셨는데... 저 코드가 어떻게 BFS가 될 수 있는지 이해하기 어렵습니다. 코드에 대한 설명을 덧붙여 주시면 개념적으로 맞고 그른지 답변해 드릴 수 있을 것 같습니다.

11년 전 link
chrak81

중간에 풀었던 과정의 코드 추가했습니다.

원래의 BFS코드라면 2번째 처럼 될 텐데, 메모리 초과가 되더라구요..
visited 변수를 없애고 graph에 0 = 방문불가, 1 = 미방문,
2 = 방문으로 풀었는데도 여전히 마찬가지였습니다.

그래서 3번째 코드처럼 링크드 리스트로 그래프 데이터를 변환해서
돌려주었는데도 시간초과가 걸리는 문제가 있었습니다.
BFS를 시작점에서 부터 한번만 검사를 하면 시작점에 관련된 것들만
그룹지어지는 문제도 있었구요..

그래서 마지막처럼 미리 queue에 데이터를 전부 대입해서 관련된 데이터
를 지워나가는 방식으로 변경해 보았습니다. 링크드 리스트의 erase의
비용이 크지 않다면 오히려 위에 소스들보다는 효율적이지 않을까 생각을
해서 말이죠...

지금 보니까 visit하는 부분을 한꺼번에 묶어서 처리해야 될 듯 싶긴 한데
맞는지요?

11년 전 link
Being

BFS의 개념을 잘못 이해하고 계신 것 같습니다. 두번째, 세번째 풀이와 같이 하시면 $O(E^2)$가 됩니다. 또한, 제한이 10만인데 1만까지만 고려하신 것으로 보입니다. 첫번째 풀이는 지수적으로 느릴 것 같네요.

11년 전 link
chrak81

아 메모리 제한 초과에 걸렸다고 나와서 너무 많이 잡았나 싶었는데
적게 잡아서 초과가 되었다는 경고였었나 보네요.. 이런... 0을 하나
빼먹다니...
참고 말씀 감사드립니다. ^{^}

11년 전 link
Being

1만으로만 잡아도 한참 메모리 제한을 넘기게 됩니다. 1억 바이트만 해도 100메가바이트입니다.

11년 전 link
chrak81

그,, 그렇죠. 초과하는게 당연한건데 0이 하나 빠졌다고 하셔서 아차해서 이상한 답변을 했었네요.
마지막 시도했던 소스 추가했습니다.
마지막 소스도 결국 O(E 2 )라 크게 개선되지 못한 채 시간초과네요...

for문을 돌린 이유가 인접한 데이터를 찾기 위함인데, (1 3)(7 4)(2 4)(5 6)(9 10)(8 6)에서
(1 3)이 다른 숫자와 인접해 있는가를 찾기 위해서는 결국 전체 루프를 돌 수 밖에 없다고
생각되어서였거든요..
BFS가 잘못된 것 같다는 말씀은 여기에 루프를 돌리지 않고 처리할 수 있는 방법이 있다는 말씀이시죠?

11년 전 link
Being

http://en.wikipedia.org/wiki/Breadth-first_search 항목 등을 참고하시기 바랍니다.

11년 전 link
chrak81

자료 감사드립니다!

11년 전 link
chrak81

문서 및 다른분이 사용하고 계시는 BFS를 참고하여 다시 작성해 보았으나 여전히 시간초과나서..
결국엔 Union-Find 써서 시간내에 풀었습니다... 42회만에 풀었네요

BFS로 시간 내로 풀 수 있을지 의문인 것이...
시험 삼아서 가장 자주 발생하는 숫자를 queue의 가장 처음에 놓고 인접한 숫자를 모두 찾는 싸이클
만 해도 시간초과가 나오더라구요... 다른 방식으로 문제는 해결했으나 여전히 뭔가 찝찝하네요.

11년 전 link
Being

코드를 살펴보았는데 여전히 잘못 이해하고 계신 것 같습니다. 아무튼 이 문제를 푸셨으니 답안 목록에서 다른 분들의 풀이를 읽으실 수 있는데요, 다른 분들은 어떻게 푸셨는지 살펴 보시면 좋은 공부가 될 것 같습니다.

11년 전 link
chrak81

길찾기 알고리즘에서 쓰이는 너비 우선 탐색으로 각인되어 있다보니
쓸데없이 해당 함수 안에서 데이터를 생성하는 우를 범했었네요.
데이터 구조의 접근 방식도 너무 비효율적이었던 것 같고...
그런데 이정도로 속도차이가 날줄은 생각도 못했습니다.
아무튼 정답 시 다른 답들도 볼 수 있어서 BFS로 구현시 잘못
되었던 점들을 찾을 수 있었습니다. 도움 감사드립니다!

11년 전 link
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.

SINCE 2007

다가오는 이벤트들

BRAVE 문제 질문있습니다.

11개의 댓글이 있습니다.