[BOJ] 백준 1376 민식우선탐색

문제 링크

www.acmicpc.net/problem/1376

1376번: 민식우선탐색

 

오랜만에 재밌게 푼 문제였습니다. 저한테 플래티넘은 아직도 버거우니 문제 풀이+후기 느낌으로 글을 씁니다.

접근

일반적인 그래프 탐색을 하되 간선을 저장하는 자료구조를 좀 특별하게 가져가야 하지 않을까 생각했습니다. 처음부터 거의 세그먼트 트리를 사용하는 쪽으로 기울었었구요.

 

우선 처음 생각했던 조건은 다음과 같습니다.

1. 어떤 정점 x에 도달했을 때, x와 연결된 모든 정점의 간선 목록에서 x를 제거해야 함
2. 어떤 정점 x에 도달했을 때, x의 간선 목록 중에서 중간값을 빠르게 구해야 함

여기서 1, 2번 조건 모두 $O(E)$ 미만으로 해결해야 한다고 생각했습니다.

왜 그렇게 생각했었는지는 모르겠지만, 특히 1번 조건에서 연결된 모든 정점에 대해 x를 제거하는 행위 자체를 $O(E)$미만으로 해결해야 한다고 생각해서 좀 오래 고민했습니다. 근데 다시 보니 모든 정점이 아니라 한 정점에서 간선 하나를 삭제하는 연산을 $O(E)$미만으로 구현해주기만 하면 되더라구요.

 

위 연산을 수행할 수 있으면서 시간 복잡도도 낮게 나오는 자료구조로 세그먼트 트리가 가장 적합했습니다.

 

풀이

우선 일반적인 방법처럼 인접 리스트로 간선 목록을 저장하고, 이를 기반으로 각 정점마다 세그먼트 트리를 구성해주면 됩니다.

이때 주의할 점이 있습니다. 데이터가 친절하지 않아 중복 간선과 자기 자신에게 간선이 꽂히는 루프 또한 존재합니다. 문제에서 주어진 홀/짝 조건은 현재 점에서 방문할 수 있는 정점을 기준으로 하기 때문에 중복 간선과 루프를 미리 제거해주어야 합니다.

 

그 후 세그먼트 트리의 쿼리 함수를 잘 짜줍니다. 방문할 수 있는 정점 중 임의의 $k$번째 정점이 어떤 정점인지 반환하도록 짜주면 됩니다. 저는 이 함수를 이분 탐색을 기반으로 range sum 쿼리를 적용해 $O(\log^2E)$로 구현하려 했는데, 홍대의 빛, 홍대의 자랑 Green55씨가 이분 탐색 없이 간단하게 $O(\log{E})$로 짤 수 있다고 알려주어 그 방식으로 구현했습니다.

 

이까지 왔으면 핵심은 완성됐습니다. 나머지는 직접 구현해봅시다!

 

후기

아래 사진은 채점 결과입니다.

처음 코드를 짜는 시간보다 시간 초과, 런타임 에러로 디버깅하는 시간이 훨씬 더 걸렸던 것 같습니다.

 

TLE 때문에 bitwise를 이용한 바텀업 세그먼트 트리, 혹은 동적 세그먼트 트리까지 고려했었는데 생각보다 간단히 해결됐습니다. 처음 설계한 풀이가 이론상 충분한 시간 복잡도를 가지므로 다른 곳에서 시간을 줄이면 되는 것이었습니다. 이를 Green55씨가 툭 던져준 Fast I/O 코드로 해결했습니다. 빛빛...

 

RTE는 정말 찾기 힘들었습니다. 늦은 시간 + 오랜 코딩으로 멘탈이 찢긴 상태에서 암만 코드를 봐도 해결할 수가 없었는데요, 다음날 맑은 정신으로 곰곰이 생각해보니 쿼리나 업데이트 코드 자체는 전혀 문제가 없다고 판단됐습니다. 그렇게 찾은 게 세그먼트 트리를 init 해주는 과정에서 어떤 정점에 연결된 간선이 없는 경우 인덱스가 꼬여 런타임 에러가 나는 부분이었습니다. 이를 간단히 수정해주니 바로 맞았습니다!! 를 받을 수 있었습니다.

 

 

사회복무요원으로 복무하게 되어 훈련소 + 근무지 적응기로 근 몇 달간 알고리즘은 손도 안 댔었는데 오랜만에 신나서 풀었더니 다시 PS가 하고싶어졌습니다. 앞으로 블로그에도 종종 글을 올리지 않을까 싶습니다.

 

정답 코드

#include <bits/stdc++.h>

#define ALL(X) X.begin(), X.end()
using namespace std;

namespace fio {
    const int BSIZE = 524288;
    char buffer[BSIZE];
    int p = BSIZE;

    inline char readChar() {
        if (p == BSIZE) {
            fread(buffer, 1, BSIZE, stdin);
            p = 0;
        }
        return buffer[p++];
    }

    int readInt() {
        char c = readChar();
        while ((c < '0' || c > '9') && c != '-') {
            c = readChar();
        }
        int ret = 0;
        bool neg = c == '-';
        if (neg) c = readChar();
        while (c >= '0' && c <= '9') {
            ret = ret * 10 + c - '0';
            c = readChar();
        }
        return neg ? -ret : ret;
    }
}

struct Node {
    vector edges, tree;
    int treeSize, numEdges; 

    void addEdge(int u) {
        edges.push_back(u);
    }

    int hasOddEdges() {
        return numEdges & 1;
    }

    int size() {
        return numEdges;
    }

    void initTree() {
        sort(ALL(edges));
        edges.erase(unique(ALL(edges)), edges.end());
        treeSize = numEdges = edges.size();
        if (treeSize == 0) return;

        tree.resize(numEdges * 4);
        initTree(1, 0, treeSize - 1);
    }

    int initTree(int node, int s, int e) {
        if (s == e) {
            return tree[node] = 1;
        }
        int m = (s + e) / 2;
        return tree[node] = initTree(node * 2, s, m) + initTree(node * 2 + 1, m + 1, e);
    }

    int query(int type) {
        if (type == 0)
            return edges[query(1, 0, treeSize - 1, 1)];
        else
            return edges[query(1, 0, treeSize - 1, numEdges / 2 + 1)];
    }

    int query(int node, int s, int e, int k) {
        if (s == e) return s;
        int leftNode = node * 2;
        int leftCnt = tree[leftNode];

        int m = (s + e) / 2;
        if (leftCnt >= k)
            return query(node * 2, s, m, k);
        else
            return query(node * 2 + 1, m + 1, e, k - leftCnt);
    }

    void removeEdge(int e) {
        int idx = lower_bound(ALL(edges), e) - edges.begin();
        update(1, 0, treeSize - 1, idx, -1);
        numEdges--;
    }

    void update(int node, int s, int e, int idx, int diff) {
        if (s <= idx && idx <= e) {
            tree[node] += diff;
            if (s != e) {
                int m = (s + e) / 2;
                update(node * 2, s, m, idx, diff);
                update(node * 2 + 1, m + 1, e, idx, diff);
            }
        }
    }
} p[111111];

int n, m;
bool chk[111111];

void dfs(int now) {
    chk[now] = true;
    cout << now << ' ';
    for (const int &e: p[now].edges) {
        p[e].removeEdge(now);
    }
    while (p[now].size() > 0) {
        int next = p[now].query(p[now].hasOddEdges());
        if (!chk[next])
            dfs(next);
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    n = fio::readInt();
    m = fio::readInt();
    for (int i = 0; i < m; i++) {
        int u, v;
        u = fio::readInt();
        v = fio::readInt();
        if (u == v) continue;
        p[u].addEdge(v);
        p[v].addEdge(u);
    }
    for (int i = 1; i < n + 1; i++) {
        p[i].initTree();
    }
    dfs(1);
}