dfs
-
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 개수를 물어보는 문제라고 ..
[백준 2583번] [DFS] 영역 구하기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 개수를 물어보는 문제라고 ..
2021.12.10 -
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_..
[백준 1743번] [DFS] 음식물 피하기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_..
2021.12.10 -
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..
[백준 11724번] [DFS] 연결 요소의 개수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..
2021.12.10 -
Approach 1개의 정점을 기준으로 1개의 outstream만 가능하므로, 각 component별로 사이클 1개와 해당 사이클을 구성하고 있는 정점을 지시하는 정점들로 구성되어 있을 수 밖에 없다. 기존에 방문 여부를 판단하기 위해서 visited배열을 이용했다면, 해당 노드를 완전히 방문했는지를 체크하기 위해서 finished 배열을 추가해주면 된다. 자세한 내용은 kks227님의 블로그를 참고해주면 된다. https://m.blog.naver.com/kks227/220785731077 깊이 우선 탐색(Depth-First Search) (수정 2019-08-18) 어후... 강의 꾸준히 쓰기 정말 힘드네요. 이번엔, 원래 3부 전에 썼어야 할 내용인 탐색에 대해 작성할 겁... blog.naver..
[백준 9466번] [DFS / Cycle] 팀 프로젝트Approach 1개의 정점을 기준으로 1개의 outstream만 가능하므로, 각 component별로 사이클 1개와 해당 사이클을 구성하고 있는 정점을 지시하는 정점들로 구성되어 있을 수 밖에 없다. 기존에 방문 여부를 판단하기 위해서 visited배열을 이용했다면, 해당 노드를 완전히 방문했는지를 체크하기 위해서 finished 배열을 추가해주면 된다. 자세한 내용은 kks227님의 블로그를 참고해주면 된다. https://m.blog.naver.com/kks227/220785731077 깊이 우선 탐색(Depth-First Search) (수정 2019-08-18) 어후... 강의 꾸준히 쓰기 정말 힘드네요. 이번엔, 원래 3부 전에 썼어야 할 내용인 탐색에 대해 작성할 겁... blog.naver..
2021.12.10 -
Approach 연결 요소(Component)의 개수를 묻는 문제이다. 배추가 심어져 있는 곳에 대해서 방문하지 않았다면 DFS / BFS를 돌리고 component의 개수를 1 증가시켜 주면 된다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; typedef pair pii; int dx[4] = {0, 0, 1, -1}; int dy[4] = {-1, 1, 0, 0}; int m, n; int edge[51][51]; int visited[51][51]; vector node; void dfs(int x_val, int y_val){ visited[x_val][y..
[백준 1012번] [DFS / BFS] 유기농 배추Approach 연결 요소(Component)의 개수를 묻는 문제이다. 배추가 심어져 있는 곳에 대해서 방문하지 않았다면 DFS / BFS를 돌리고 component의 개수를 1 증가시켜 주면 된다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; typedef pair pii; int dx[4] = {0, 0, 1, -1}; int dy[4] = {-1, 1, 0, 0}; int m, n; int edge[51][51]; int visited[51][51]; vector node; void dfs(int x_val, int y_val){ visited[x_val][y..
2021.12.09 -
간단한 DFS문제이다. 사실 생각해보면 M을 기준으로 사이클 돌때를 판단해주면 된다. 주의해야할 지점은 바라보는 지점과 처리해야 하는 지점이 다르다는 것이다. 반복여부를 판단하기 위해서는 시작지점을 봐야하고, 문제에서 필요로하는 데이터는 1사이클의 마지막 데이터이기 때문이다. 다만, 일반적으로는 끝나는 데이터가 다시 시작지점이 되므로 이 부분을 핸들링해주면 되지만, 만약 1이 끝나는 지점의 경우는 예외 케이스가 발생할 수 있으므로 따로 처리해주면 된다. 추가적으로 가장 골치 아픈 지점이 다시 1로 돌아오는 것이 아니라 다른 지점으로 사이클을 형성하는 것이다. 이 부분을 해결하기 위해서 여러가지 방법이 있을 수 있다. pair 자료구조 등을 활용해서 처리할 수 있고 여러가지 방법이 존재한다. 따로 뺴서 계..
[백준 5829번] [DFS] Luxury River Cruise간단한 DFS문제이다. 사실 생각해보면 M을 기준으로 사이클 돌때를 판단해주면 된다. 주의해야할 지점은 바라보는 지점과 처리해야 하는 지점이 다르다는 것이다. 반복여부를 판단하기 위해서는 시작지점을 봐야하고, 문제에서 필요로하는 데이터는 1사이클의 마지막 데이터이기 때문이다. 다만, 일반적으로는 끝나는 데이터가 다시 시작지점이 되므로 이 부분을 핸들링해주면 되지만, 만약 1이 끝나는 지점의 경우는 예외 케이스가 발생할 수 있으므로 따로 처리해주면 된다. 추가적으로 가장 골치 아픈 지점이 다시 1로 돌아오는 것이 아니라 다른 지점으로 사이클을 형성하는 것이다. 이 부분을 해결하기 위해서 여러가지 방법이 있을 수 있다. pair 자료구조 등을 활용해서 처리할 수 있고 여러가지 방법이 존재한다. 따로 뺴서 계..
2021.02.10 -
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..
[백준 1167번] [트리] 트리의 지름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..
2020.11.24 -
이 문제의 경우에는 사실 트리보다는 DFS를 활용하는 것에 가깝다. 처음에 접근한 방법은 루트 노드를 바탕으로 재귀를 통해 DFS처리하면서 가중치 최댓값들을 찾아나가는 방법이다. 하지만, 잘 생각해보면 루트 노드가 고정되어 있는 것처럼 표현하지만 어떠한 노드를 잡아도 루트화 시킬 수 있다.(적절하게 변형하면 된다.) 즉, 모든 노드에 대하여 재귀를 통해 DFS처리하면서 가중치 최댓값들을 찾고, 그 중 최댓값을 출력해주면 된다. 해당하는 내용을 토대로 코드를 구현한 결과는 다음과 같다. #include #include #include #include using namespace std; struct node{ vector path_store; }; int checker(node *data_store, in..
[백준 1967번] [트리] 트리의 지름이 문제의 경우에는 사실 트리보다는 DFS를 활용하는 것에 가깝다. 처음에 접근한 방법은 루트 노드를 바탕으로 재귀를 통해 DFS처리하면서 가중치 최댓값들을 찾아나가는 방법이다. 하지만, 잘 생각해보면 루트 노드가 고정되어 있는 것처럼 표현하지만 어떠한 노드를 잡아도 루트화 시킬 수 있다.(적절하게 변형하면 된다.) 즉, 모든 노드에 대하여 재귀를 통해 DFS처리하면서 가중치 최댓값들을 찾고, 그 중 최댓값을 출력해주면 된다. 해당하는 내용을 토대로 코드를 구현한 결과는 다음과 같다. #include #include #include #include using namespace std; struct node{ vector path_store; }; int checker(node *data_store, in..
2020.11.23