방향그래프에서 한붓그리기 (Eulerian Path) 구하기

http://koistudy.net/?mid=prob_page&NO=521

알고리즘 문제해결 전략에 나온거랑 되게 비슷한 문제다. 그래서 베끼다시피해서 제출했다

문제에 사족이 참 많은데 요약하자면 모든 단어을 사용해서 끝말잇기를 하라 라는 내용이다.

단, 한 단어는 00 ~ 99 낱말 5개 로 구성되었으며, 출력시 사전순으로 가장 앞서는 것을 출력해야 한다.

단어를 꼭지점 (vertex)로 두고 생각하면 백트래킹을 해야 하기 때문에 500000개는 택도 없다.

거기다 지금 이 글의 주제가 한붓그리기이므로, 단어를 방향이 있는 모서리 (edge) 로 두고 한붓그리기를 하는 것이 좋겠다.

즉 단어가 0001020304 이런 식이라면, 00 -> 04로 가는 간선인 것이다.

그러면 V = 100, E <= 500000 이고, 이 그래프에서 한붓그리기를 하면 된다.

참 막막한데, 일단 한붓그리기를 할 수 있는 조건부터 찾자.

한붓그리기를 하려면

 * indegree - outdegree = 1인 시작점과 indegree - outdegree = -1인 도착점이 하나씩만 있거나

 * 모든 점의 indegree 가 outdegree와 같다

고등학교 수학에서 차수가 짝수일 경우 한붓그리기가 가능하다는 내용을 방향그래프에 맞게 조금 더 엄밀히 정의한 것이다. 이 조건이 아닐 경우 impossible을 띄운다.

이제 한붓그리기를 시작하자.

한붓그리기는 어느 간선에서나 시작해도 상관이 없으니, 그냥 아무 간선이나 잡고 아무 곳이나 가면 된다.

그러면 아마 간선이 많이 빠져있긴 하겠지만, 도착점에 (혹은 시작점) 에 도착하긴 할것이다.

그림이 혐짤 수준인데 ;;;

아무튼 1 -> 2 -> 1로 돌아오긴 할것이다.

우리의 목표는 3과 4를 경로에 끼워넣는 것이다.

어떻게 하면 3과 4를 경로에 끼워넣을 수 있을까?

아마 한바퀴 도는 과정에서 3과 4를 발견하면 그걸 경로에 넣고 순회하면 되지 않을까?

void f(int pos){
    for each edge starting from pos{
        delete edge;
        route += f(r % 100);
    }
}

(갔다온 간선은 지워줘야 한다. 한붓그리기라는 점을 잘 생각해보면 남겨둘 의미가 전혀 없다.

저걸 실제로 구현할때는 pos를 나오면서 경로에 저장시켜주면 된다. 여기서는 데큐를 써서 간선을 지웠다.

void f(int pos){
    while (!graph[pos].empty()) {
        long long r = graph[pos].front()%100;
        graph[pos].pop_front();
        f((int)r);
    }
    res.push_back(pos);
}

그러면 이런 코드가 나오고, 경로가 역으로 저장된다.

경로는 거꾸로 읽으면서 알아서 알파벳 순서대로 출력하면 된다.

... 라고 하면 될 거 같아 보이고 실제로도 보통 되지만,

여기서는 중요한 변수가 하나 있는데 바로 재귀가 터진다는 점이다 ㅡㅡ;

스택을 써서 재귀를 풀어주자.

void f(int pos){
    stack s;
    s.push(pos);
    int upd = 0;
    while (!s.empty()) {
        upd = 0;
        pos = s.top();
        while (!graph[pos].empty()) {
            long long r = graph[pos].front()%100;
            graph[pos].pop_front();
            s.push((int)r);
            upd = 1;
            break;
        }
        if(upd == 1) continue;
        s.pop();
        res.push_back(pos);
    }
}

이렇게 코드를 적절히 짜면 Accept를 먹일 수 있다.