[TIL] 24.01.30

1. 알고리즘 문제 해결

 

 

트리의 지름(백준 1167):

 정점의 개수가 100,000개까지 들어올 수 있기 때문에, 브루트 포스나 인접행렬을 이용할 순 없다. 가장 긴 거리를 이루는(사이의 가중치가 큰) 두 정점 중 하나를 알 수 있다면, 그 정점에서 DFS로 가장 멀리 있는 정점을 찾아낼 수가 있다. 그래서 두 정점 중 하나를 알아내는 방법을 떠올리는 것이 핵심이라고 생각했다.

 트리에서 지름을 이루는 부분을 일자로 길게 펼친다고 생각해보면, 트리 내의 어떤 정점에서든 가장 멀리 떨어진 정점이 지름을 구성하는 두 정점 중 하나라는 사실을 직관적으로 떠올릴 수 있다.

 이를 바탕으로 구현하기 위해 특정 정점에서부터 가장 멀리 떨어진 정점 및 그 가중치 합을 리턴하는 DFS 함수를 만들었다. 그리고 1번 정점을 대입해 지름의 끝을 하나 찾고, 다시 그 정점을 DFS 함수에 대입해서 트리의 지름을 찾아내는 방식으로 구현했다.

#include <iostream>

#include <vector>

#include <algorithm>

#include <stack>

using namespace std;

vector<vector<pair<int, int> > > adjacentVector;

int v;

pair<int, int> DFS(int start) {

    pair<int, int> farLeaf = {0,0};

    stack<pair<int, int> > st;

    vector<bool> isVisited(v+1, false);

    st.push({start, 0});

    while(!st.empty()) {

        pair<int, int> topP = st.top();

        st.pop();

        isVisited[topP.first] = true;

        if(topP.second > farLeaf.second) {

            farLeaf = topP;

        }

        for(auto node: adjacentVector[topP.first]) {

            if(!isVisited[node.first]) {

                st.push({node.first, topP.second+node.second});

            }

        }

    }

    return farLeaf;

}

int main() {

    cin.tie(nullptr);

    ios_base::sync_with_stdio(false);

    cin >> v;

    adjacentVector = vector<vector<pair<int, int> > >(v+1);

    for(int i=0; i<v; i++) {

        int startVertex;

        int targetVertex, dist;

        cin >> startVertex >> targetVertex;

        while(targetVertex!=-1) {

            cin >> dist;

            adjacentVector[startVertex].push_back({targetVertex, dist});

            cin >> targetVertex;

        }

    }

    int farLeaf = DFS(1).first;

    cout << DFS(farLeaf).second;

}

 

 

 

 

 

DFS와 BFS(백준 1260):

 문제 이름처럼 DFS와 BFS를 구현하면 되는 문제. 방문 가능한 정점이 여러 개일 때, 정점 번호가 작은 것을 먼저 방문해야 하기도 하고, 정점의 개수도 최대 1,000개까지만 주어지기 때문에 인접행렬을 사용하는게 편하다. 스택과 큐를 이용해 일반적인 DFS와 BFS를 구현하면 바로 해결된다.

 

 

 

2. 안드로이드 공부

 

Compose의 Lazy Grids를 잘 이용하면 적응형 UI나 다양한 컴포넌트들을 유동적으로 구성할 때 편리하다. 만약 LazyVerticalGrid라면 columns인자에 GridCells 객체를 넣을 수가 있다. 이 때, GridCells.Adaptive()를 이용한다면 유동적으로 디스플레이 해상도에 맞춰 column 수가 구성된다. 또 컴포넌트가 다양할 경우, items를 설정할 때 span 값을 적절하게 줄 수 있다. 지금 만들어보고 있는 쇼핑몰 앱 등을 구성할 때 특히 유용하다.