PS 일기 2024년 1월 31일 (2일 차) (1376번 민식우선탐색)

게시 2024/01/31

By seungchan lee

5 분읽는 시간

PS 일기 2024년 1월 31일 (2일 차)

PS 일기란?

PS 실력 향상을 목적으로 날마다 푼 문제를 회고하는 것입니다. 문제의 간단한 해법과 함께 어떤 방식으로 접근했는지, 그리고 문제의 해법을 찾는 데 결정적이었던 깨달음은 무엇이었는지 등을 기록합니다.

오늘의 문제

1376번 민식우선탐색

알고리즘 분류

Segment Tree
Binary Search
DFS

문제 설명

그래프가 주어지고 1번 정점을 시작으로 민식우선탐색의 결과를 출력합니다. 민식우선탐색은 다음과 같습니다.

기본적으로 DFS와 유사합니다. 다만 방문하는 순서가 다릅니다.
방문할 수 있는 정점의 개수가 홀수이면 그 정점 번호의 중간값인 정점에 방문합니다.
방문할 수 있는 정점의 개수가 짝수이면 가장 작은 정점번호의 정점으로 방문합니다.

문제 풀이

관측 1

세그먼트 트리를 이용하여 중간값의 정점 번호, 가장 작은 정점 번호를 빠르게 구할 수 있습니다.

세그먼트 트리를 이용하면 중간값, 가장 작은 값을 빠르게 구할 수 있습니다. 물론 이분탐색을 이용하여 빠르게 구할 수 도 있겠지만 방문한 정점을 지우려면 이분탐색은 느립니다. 펜윅트리를 사용해도 좋습니다. 또 BST로도 될 수 있을 것 같습니다.

관측 2

문제는 사이클입니다.

정점 $u$와 직접 연결되어 있는 정점을 $v$, $w$라 했을 때 $u$에서 탐색을 시작하여 $v$에 방문하면 $u$에서 $w$의 방문 여부를 알아야 탐색을 정상적으로 할 수 있습니다. 이는 $v$와 $w$가 직접 또는 간접적으로 연결되어 있을 수 있기 때문입니다. 하지만 이 경우를 잘 살펴보면 사이클이 존재하는 경우인 것을 알 수 있습니다. 따라서 탐색하며 직접 연결된 정점 중 이미 방문을 한 정점이 있다면 그 방문한 정점에 탐색 중인 정점을 방문하였다고 표시하면 됩니다.

구현

모든 노드에 대하여 $n$만큼의 크기로 세그먼트 트리 만든다면 메모리 초과가 날것이 뻔하기 때문에 각 노드에 대하여 연결의 개수만큼만 만들고, 연결의 저장 순서를 정점 번호로 정렬한 후 이분 탐색을 하여 세그먼트 트리에서 특정 정점에 해당하는 위치를 찾았습니다.

  
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100005;

int n, m;
bool visited[MAXN];
vector<int> graph[MAXN];
vector<int> trees[MAXN];

void update(int tree, int start, int end, int index, int pos, int value)
{
    if(end < pos || pos < start) return;

    if(start == end) {
        trees[tree][index] = value;
        return;
    }

    int mid = (start + end) / 2;
    update(tree, start, mid, 2*index, pos, value);
    update(tree, mid+1, end, 2*index+1, pos, value);
    trees[tree][index] = trees[tree][2*index] + trees[tree][2*index+1];
}

int kth(int tree, int start, int end, int index, int k)
{
    if(start == end) return start;
    
    int mid = (start + end) / 2;

    if(k <= trees[tree][2*index]) {
        return kth(tree, start, mid, 2*index, k);
    } else {
        return kth(tree, mid+1, end, 2*index+1, k - trees[tree][2*index]);
    }
}

void mFS(int node)
{
    cout << node << " ";
    visited[node] = true;
    trees[node].resize(4*graph[node].size());
    for(int i = 0; i < graph[node].size(); i++) {
        if(visited[graph[node][i]]) {
            int pos = lower_bound(graph[graph[node][i]].begin(), graph[graph[node][i]].end(), node) - graph[graph[node][i]].begin();
            update(graph[node][i], 0, graph[graph[node][i]].size() - 1, 1, pos, 0);
        } else {
            update(node, 0, graph[node].size() - 1, 1, i, 1);
        }
    }

    while(0 < trees[node][1]) {
        int k = (trees[node][1] & 1) ? trees[node][1] / 2 + 1 : 1;
        int next = graph[node][kth(node, 0, graph[node].size() - 1, 1, k)];
        mFS(next);
    }
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        if(u == v) continue;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    for(int i = 1; i <= n; i++) {
        sort(graph[i].begin(), graph[i].end());
        graph[i].erase(unique(graph[i].begin(), graph[i].end()), graph[i].end());
    }


    mFS(1);
}

PS 일기