Approach Component 개수를 물어보는 문제이다. 기본적인 접근 방법은 다음 문제와 거의 유사하다. 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 처음에는 DFS를 돌 되, 스택을 활용해서 자신보다 밑에 있는 element 들은 방문할 수 있다는 점을 활용해서 component별로 처리하려고 했는데 사이클이 존재할 수 있는 측면때문에 실패하였다. 물론 코드를 잘(?) 짜면 가능할 것 같기도 하다. 기본적인 접근 방법은 모든 노드들에 대해서 dfs를 돌면서, 방문할 수 있는 노드를 찾아나가면 된다. 다만, 유의할 지점이 사이클이 존재할 수 있기 때문에 자기 자신으로 돌아오는 간선이 있으면 따로 체크해주어야 한다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int r[100][100]; int ..

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..

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..

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..