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 문제에서 주어진 트리 그림을 잘 보면, 너비 번호가 중위순회를 통해 방문하는 순서와 완벽하게 동일함을 쉽게 파악할 수 있다. 추가적으로 같은 높이 기준으로 넓이가 가장 최대인 것을 찾고 싶은 상황이므로 dfs를 하는 정점의 높이가 어떻게 되는지를 트래킹 해야한다. 따라서 dfs의 parameter에 높이 정보를 추가로 주입해주면 된다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; class tree{ public: int left; int right; tree() : left(-1), right(-1) {} tree(int x, int y) : le..

Approach 사실 예제 입력 2에 대한 설명을 보고 가장 큰 아이디어를 얻었다. 문제에서 1번으로 가는 길은 유일하다는 표현을 통해 사이클이 없는 트리 구조임을 쉽게 파악할 수 있다. 따라서 점들의 관계를 표시해보면, 일종의 1번 노드를 루트 노트로 하는 트리로 이해할 수 있다. 그런데, 자식 노드를 기준으로 점차적으로 위로 올라오면서 양이 들어오는 양상이다. 추가적으로 해당 점이 양이 있는 곳이라면 자식에서 올라오는 양의 수에 해당 점에 있는 양의 수를 더해주면 되고, 반대로 늑대가 있는 점이라면 자식에서 올라오는 양의 수에 해당 점에 있는 늑대의 수를 뺴주면 된다. (만약 음수가 나올 경우에는 0으로 만들어주면 된다.) 늑대는 이동하지 않는 상황이므로 dfs를 돌면서 양의 값을 ret으로 잡으면 ..

다시 사용될 수 있는 아이디어나 발상들을 따로 정리해둔 글이다. 1. 백준 16437번 (https://viyoung.tistory.com/343) - 그래프 상에서 두 정점 사이에 유일한 경로가 있다는 의미는 트리 구조라는 의미이다. (사이클이 존재하지 않는다.) 2. 백준 4803번 (https://viyoung.tistory.com/341) - 그래프 상에서 트리 구조임을 직접 확인하는 방법. (간선을 추가할 때, 시점과 종점을 바꾼 간선도 추가해줘서 파악) 3. 백준 1967번 (https://viyoung.tistory.com/110) - 루트로부터 가장 멀리 있는 정점을 아무거나 찾고, 그 정점으로부터 가장 먼 정점과의 거리가 트리의 지름이다. (증명 : https://m.blog.naver...

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

Approach 문제 설명이 난해해서 꽤 많이 틀렸다.. 일단, 연산을 k번 했을 때의 상황을 묻는 것이므로 BFS문제임을 쉽게 직감할 수 있다. 기본적으로 다음 문제 컨셉과 비슷하기 때문이다. https://viyoung.tistory.com/338 [백준 9019번] [BFS] DSLR Approach 최소한의 명령어를 찾는 것이므로 BFS를 활용하면 된다는 것을 쉽게 파악할 수 있다. https://viyoung.tistory.com/337 이 문제와 접근방법이 매우 유사하다. [백준 16397번] [BFS] 탈출 Approach 잘 생.. viyoung.tistory.com 이 문제가 좀 어려운 이유는 정확히 K번 움직였을 때 나올 수 있는 수들 중 최댓값을 구해야한다는 지점이다. 왜냐하면 단순히..

Approach 최소 이동 횟수를 물어보는 지점에서 BFS 문제를 추측할 수 있다. 이 경우에는 이동하는 기준이 3 x 3 상태이다. 따라서 해당 3 x 3 배열을 일종의 정점처럼 취급하여 BFS를 돌리면 된다. (0의 위치를 기준으로 탐색을 해도 된다는 생각이 들 수 있으나, 0의 위치가 같아도 행렬이 달라질 수 있기 때문에 이 방법으로는 이 문제를 풀 수 없다.) 다만, 배열을 직접적으로 넣으면 메모리 초과에 걸리므로 string 자료형을 활용하여서 메모리를 상당히 줄였다. BFS에 들어가는 정보가 좌표가 아니라 배열이라는 점이 매우 독특했던 문제이다. (참고 : https://blog.naver.com/kks227/220785747864) 너비 우선 탐색(Breadth-First Search) (수..

Approach 최소한의 명령어를 찾는 것이므로 BFS를 활용하면 된다는 것을 쉽게 파악할 수 있다. https://viyoung.tistory.com/337 이 문제와 접근방법이 매우 유사하다. [백준 16397번] [BFS] 탈출 Approach 잘 생각해보면 최대 T번 누를 수 있다는 명제를 T번 이동할 수 있다로 바꾸고, 버튼 A와 B를 누르고 나오는 숫자를 기준으로 생각해보면 비둘기집의 원리에 따라서 총 99999가지 경우의 수 viyoung.tistory.com 기본적으로 숫자를 기준으로 방문배열을 체크해야한다는 점에서 완전히 동일하다. 다른 지점은, 명령어를 기억해야한다는 점인데 큐에 넣을 때 해당 명령어를 기억하게끔 하면 쉽게 처리할 수 있다. 다른 접근 방법으로는 prev 정보를 저장하는..