Approach 트리의 지름과 동일한 문제이다. 맨 마지막에 "The labyrinth is designed in such a way that there is exactly one path between any two free blocks"라고 했으므로 사이클이 없는 그래프이므로 트리 구조를 띄고 있음을 쉽게 파악할 수 있다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; typedef pair ii; int move_x[4] = {-1, 1, 0, 0}; int move_y[4] = {0, 0, -1, 1}; bool r[1000][1000]; bool visite..

Approach 조금은 발상적일 수 있는데, 간선을 2번 방문하지 않는 경우는 가장 오른쪽 노드들을 방문할 때가 유일하다. 따라서 트리의 간선의 수는 component에 속한 정점의 수 - 1이라는 것을 생각해보면 해당 값의 2배에서 맨 오른쪽 노드들을 방문하는 간선들의 개수만큼을 제거해주면 된다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; bool visited[100001]; class tree{ public: int l; int r; tree() : l(-1), r(-1) {} tree(int a, int b) : l(a), r(b) {} }; vector ..

Approach 자료구조 수업에서나 나올법한 문제이다. 잘 생각해보면 preorder가 하는 역할을 잘 생각해보면, 루트 노트부터 시작해서 왼쪽 방향무터 서브트리의 루트노드를 지속적으로 방문하게 된다. 따라서 해당 순서를 inorder에서 바라보게 되면, 발견한 index를 기준으로 왼쪽은 자신을 기준으로 왼쪽과 오른쪽으로 subtree를 나누어서 생각할 수 있다. 세그트리 짜는 것처럼, start, end index를 함수의 입력값으로 두고 계속해서 좁혀가면 쉽게 구할 수 있다. Code #include #define fastio ios_base::sync_with_stdio(0). cin.tie(0), cout.tie(0) using namespace std; vector preorder; vecto..

Approach 트리의 개수는 전체 component 개수에서 사이클을 가지는 component 개수를 제외해주면 된다. Component 개수를 구하는 것은 dfs를 호출하는 횟수와 동일하므로, 사이클이 발생하는지 여부만 체크해주면 된다. 앞에서 풀었던 문제들과 달리 한 정점에서 반드시 사이클을 지시하고 있지는 않은 상황이므로(https://viyoung.tistory.com/327) [백준 10265번] [DFS / SCC] MT Approach 위 문제에서 나타나게 되는 그래프를 잘 관찰해보면 사이클이 반드시 등장하게 되는 것을 관찰할 수 있다. 즉 1개의 Component를 기준으로 사이클이 존재하고 해당 사이클에 속한 노드를 viyoung.tistory.com 무작정 사이클이 나타날때까지 계속해..

처음에 루트노드가 0으로 고정인줄 알고 실수하였다.. 문제 자체는 되게 단순하다. 1. 트리를 구성하고 2. 특정 노드를 끊는다.(위 기준으로 끊으면 어차피 아래에 접근이 안된다.) 즉, parent node를 기준으로 해당 node를 끊어주기만 하면 된다. 다만, 가장 최상단 root node를 제거하는 경우는 따로 예외처리하도록 하자. #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); using namespace std; int arr[51][51]; int N; int dfs(int start){ bool check = true; int count = 0; for(int i = 0; i < N; i ++){ ..

1967과 동일한 알고리즘으로 접근해주면 된다. 구현 방법에 대해서 잘 기억해두도록 하자. #include #include #include #include using namespace std; struct node{ vector len_store; }; int visited[100001] = {0}; int end_point; int result; void tree_checker(node *data_store, int start, int length){ if(visited[start] != 0) return; visited[start] = 1; if(result < length){ end_point = start; result = length; } for(int i = 0; i < data_store[s..

종만북에서 본 적이 있는 유형이라 쉽게 푼 편이다. 이분트리 탐색의 경우에는 재귀를 활용해줘서 처리해주면 된다. 부분과 전체를 보면서 코드를 구현할 수 있어야 한다. 이 문제를 요약하면 전위 순회를 후위 순회로 돌려야하는 것이다. 이분트리를 보면 각 노드를 기준으로 왼쪽은 자신보다 더 작고, 오른쪽은 자신보다 크다. 이러한 성질은 전체적으로 보아도 성립하고 최소 단위로 보아도 성립한다. 즉, 전위 순회를 한 데이터를 기준으로 자신보다 큰 숫자가 나올 때 그것이 오른쪽 노드의 시작을 의미함을 이해할 수 있다. 그러므로 자신보다 큰 숫자가 어느 시점에 나오는지를 확인하고 그것을 기준으로 왼쪽과 오른쪽 노드를 구분하면 된다. 후위 순회의 경우, 이 과정에서 자식 노드의 왼쪽과 오른쪽을 출력하고 자기자신을 출력..

이 문제의 경우에는 사실 트리보다는 DFS를 활용하는 것에 가깝다. 처음에 접근한 방법은 루트 노드를 바탕으로 재귀를 통해 DFS처리하면서 가중치 최댓값들을 찾아나가는 방법이다. 하지만, 잘 생각해보면 루트 노드가 고정되어 있는 것처럼 표현하지만 어떠한 노드를 잡아도 루트화 시킬 수 있다.(적절하게 변형하면 된다.) 즉, 모든 노드에 대하여 재귀를 통해 DFS처리하면서 가중치 최댓값들을 찾고, 그 중 최댓값을 출력해주면 된다. 해당하는 내용을 토대로 코드를 구현한 결과는 다음과 같다. #include #include #include #include using namespace std; struct node{ vector path_store; }; int checker(node *data_store, in..