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 Component 개수를 물어보는 문제이다. 적록색약이 아닌 경우와 적록색약인 경우에 대해 각각 component 개수를 따로 구해주면 된다. 주의할 지점은 적록색약의 경우 R, G를 구분하지 못한다는 점이다. 따라서 R과 G사이에 이동할 수 있다는 점만 고려해주면 된다. (모듈러 연산을 통해 쉽게 처리하였다.) Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; // 0 : red, 1 : blue, 2 : green int r[101][101]; int visited[101][101]; int n; int move_x[4] = {-1, 1, 0, 0};..

Approach 사실상 이 문제와 거의 동일하다. https://viyoung.tistory.com/317 [백준 1012번] [DFS / BFS] 유기농 배추 Approach 연결 요소(Component)의 개수를 묻는 문제이다. 배추가 심어져 있는 곳에 대해서 방문하지 않았다면 DFS / BFS를 돌리고 component의 개수를 1 증가시켜 주면 된다. Code #include #define fastio ios_b.. viyoung.tistory.com 단, 유기농 배추 문제와 달리 이동할 수 있는 노드를 직접적으로 제시하지 않고 이동할 수 없는 노드들을 제시했다는 점에서만 차이가 존재한다. 근본적인 접근 방법은 완전히 동일하다고 할 수 있다. 결과적으로 Component 개수를 물어보는 문제라고 ..

Approach 이 문제와 거의 비슷하다. https://viyoung.tistory.com/317?category=884242 [백준 1012번] [DFS / BFS] 유기농 배추 Approach 연결 요소(Component)의 개수를 묻는 문제이다. 배추가 심어져 있는 곳에 대해서 방문하지 않았다면 DFS / BFS를 돌리고 component의 개수를 1 증가시켜 주면 된다. Code #include #define fastio ios_b.. viyoung.tistory.com 다만. Component 개수를 물어보는 것이 아니라 component안에 속한 원소 개수의 최대값이므로 이를 dfs 반환값을 통해 구해주면 된다. Code #include #define fastio ios_base::sync_..

Approach 다른 Component의 경우 DFS 탐색을 통해 방문할 수 없다는 점을 이용해주면 된다. 모든 정점에 대해서 방문하지 않았으면, dfs를 돌리고 component 개수를 1개씩 올려나가면 원하는 답을 도출시킬 수 있다. component에 대해서는 다음 블로그를 참고하도록 하자. https://m.blog.naver.com/kks227/220785731077 깊이 우선 탐색(Depth-First Search) (수정 2019-08-18) 어후... 강의 꾸준히 쓰기 정말 힘드네요. 이번엔, 원래 3부 전에 썼어야 할 내용인 탐색에 대해 작성할 겁... blog.naver.com Code #include #define fastio ios_base::sync_with_stdio(0), ci..