dfs
-
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..
[백준 2250번] [DFS] 트리의 높이와 너비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..
2021.12.17 -
Approach 사실 예제 입력 2에 대한 설명을 보고 가장 큰 아이디어를 얻었다. 문제에서 1번으로 가는 길은 유일하다는 표현을 통해 사이클이 없는 트리 구조임을 쉽게 파악할 수 있다. 따라서 점들의 관계를 표시해보면, 일종의 1번 노드를 루트 노트로 하는 트리로 이해할 수 있다. 그런데, 자식 노드를 기준으로 점차적으로 위로 올라오면서 양이 들어오는 양상이다. 추가적으로 해당 점이 양이 있는 곳이라면 자식에서 올라오는 양의 수에 해당 점에 있는 양의 수를 더해주면 되고, 반대로 늑대가 있는 점이라면 자식에서 올라오는 양의 수에 해당 점에 있는 늑대의 수를 뺴주면 된다. (만약 음수가 나올 경우에는 0으로 만들어주면 된다.) 늑대는 이동하지 않는 상황이므로 dfs를 돌면서 양의 값을 ret으로 잡으면 ..
[백준 16437번] [분할 정복 / DFS] 양 구출 작전Approach 사실 예제 입력 2에 대한 설명을 보고 가장 큰 아이디어를 얻었다. 문제에서 1번으로 가는 길은 유일하다는 표현을 통해 사이클이 없는 트리 구조임을 쉽게 파악할 수 있다. 따라서 점들의 관계를 표시해보면, 일종의 1번 노드를 루트 노트로 하는 트리로 이해할 수 있다. 그런데, 자식 노드를 기준으로 점차적으로 위로 올라오면서 양이 들어오는 양상이다. 추가적으로 해당 점이 양이 있는 곳이라면 자식에서 올라오는 양의 수에 해당 점에 있는 양의 수를 더해주면 되고, 반대로 늑대가 있는 점이라면 자식에서 올라오는 양의 수에 해당 점에 있는 늑대의 수를 뺴주면 된다. (만약 음수가 나올 경우에는 0으로 만들어주면 된다.) 늑대는 이동하지 않는 상황이므로 dfs를 돌면서 양의 값을 ret으로 잡으면 ..
2021.12.17 -
Approach 맨 처음 접근은 모든 벽에 대해서 BFS나 DFS를 수행하는 것이였다. 일종의 브루트포스적인 접근이였는데, 이 경우 시간초과가 발생하게 된다. 조금 더 단순하게 접근하면, 해당 벽을 기준으로 상하좌우의 component를 연결하는 느낌으로 이해해주면 된다. 이를 위해서는 각 위치에서 어떠한 component에 속하는지를 알아야하고, 각 component 별로 속한 개수를 따로 저장해두면 된다. 발상은 https://viyoung.tistory.com/327의 2번째 접근 방법을 풀어봤던 경험을 바탕으로 쉽게 할 수 있었다. 일종의 visited 배열을 component에 대응시키는 배열로 사용한 것이다. [백준 10265번] [DFS / SCC] MT Approach 위 문제에서 나타나게..
[백준 16946번] [DFS] 벽 부수고 이동하기 4Approach 맨 처음 접근은 모든 벽에 대해서 BFS나 DFS를 수행하는 것이였다. 일종의 브루트포스적인 접근이였는데, 이 경우 시간초과가 발생하게 된다. 조금 더 단순하게 접근하면, 해당 벽을 기준으로 상하좌우의 component를 연결하는 느낌으로 이해해주면 된다. 이를 위해서는 각 위치에서 어떠한 component에 속하는지를 알아야하고, 각 component 별로 속한 개수를 따로 저장해두면 된다. 발상은 https://viyoung.tistory.com/327의 2번째 접근 방법을 풀어봤던 경험을 바탕으로 쉽게 할 수 있었다. 일종의 visited 배열을 component에 대응시키는 배열로 사용한 것이다. [백준 10265번] [DFS / SCC] MT Approach 위 문제에서 나타나게..
2021.12.15 -
Approach 위 문제에서 나타나게 되는 그래프를 잘 관찰해보면 사이클이 반드시 등장하게 되는 것을 관찰할 수 있다. 즉 1개의 Component를 기준으로 사이클이 존재하고 해당 사이클에 속한 노드를 종점으로 하는 간선을 outdegree로 가지는 노드들이 존재하는 양상을 띄고 있다. 1개의 Component를 기준으로 사이클에 존재하는 것들은 서로서로 순환적으로 요구하고 있으므로 모두 다 버스에 타거나 전부 타지 말아야 한다. 따라서 해당 특성을 잘 고려하면 해당 component에서 버스를 탈 수 있는 인원은 사이클에 속한 사람 ~ 해당 component에 속한 사람이 된다. 그리고 최대 인원이 k명이라는 점을 잘 생각해보면 0/1 knapsack 문제와 비슷한 점을 발견할 수 있다. 왜냐하면 해..
[백준 10265번] [DFS / SCC] MTApproach 위 문제에서 나타나게 되는 그래프를 잘 관찰해보면 사이클이 반드시 등장하게 되는 것을 관찰할 수 있다. 즉 1개의 Component를 기준으로 사이클이 존재하고 해당 사이클에 속한 노드를 종점으로 하는 간선을 outdegree로 가지는 노드들이 존재하는 양상을 띄고 있다. 1개의 Component를 기준으로 사이클에 존재하는 것들은 서로서로 순환적으로 요구하고 있으므로 모두 다 버스에 타거나 전부 타지 말아야 한다. 따라서 해당 특성을 잘 고려하면 해당 component에서 버스를 탈 수 있는 인원은 사이클에 속한 사람 ~ 해당 component에 속한 사람이 된다. 그리고 최대 인원이 k명이라는 점을 잘 생각해보면 0/1 knapsack 문제와 비슷한 점을 발견할 수 있다. 왜냐하면 해..
2021.12.13 -
Approach DFS를 통해 트리의 높이를 추적하는 느낌이다. 다만, 사이클이 발생하는 경우에만 -1을 출력해주면 된다. 사이클이 발생하는 상황은 방문한 곳에 다시 방문을 시도하려고 할 때, -1을 출력해주면 된다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int n, m, p; int visited[100001]; int v[100001]; int r[100001]; int dfs(int c){ visited[c] = 1; if(v[c] == -1) return 0; int cur = r[v[c]]; int result = 0; if(!visited[cur]..
[백준 10552번] [DFS] DOMApproach DFS를 통해 트리의 높이를 추적하는 느낌이다. 다만, 사이클이 발생하는 경우에만 -1을 출력해주면 된다. 사이클이 발생하는 상황은 방문한 곳에 다시 방문을 시도하려고 할 때, -1을 출력해주면 된다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int n, m, p; int visited[100001]; int v[100001]; int r[100001]; int dfs(int c){ visited[c] = 1; if(v[c] == -1) return 0; int cur = r[v[c]]; int result = 0; if(!visited[cur]..
2021.12.12 -
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 개수의 변화를 보고 그 중 최댓값을 출력해준다는 점에서만 차이가 존재한다..
[백준 2468번] [DFS] 안전 영역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 개수의 변화를 보고 그 중 최댓값을 출력해준다는 점에서만 차이가 존재한다..
2021.12.11 -
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 ..
[백준 11403번] [DFS] 경로 찾기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 ..
2021.12.11 -
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};..
[백준 10026번] [DFS} 적록색약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};..
2021.12.10