반응형 dfs26 백준 2933번 미네랄 - C++ 풀이 1. 바닥에서 시작하는 DFS/BFS로 떠있는 미네랄인지 체크할 수 있다. 2. 떠있는 미네랄들에 대해서 아랫부분이 어딘가에 닿을 때까지 떨어뜨린다. 1. 바닥에서 시작하는 DFS/BFS로 떠있는 미네랄인지 체크할 수 있다. 인접한 미네랄은 하나의 클러스터이므로, 바닥에서 DFS/BFS를 시작하여 방문하지 못한 미네랄은 떠있는 미네랄로 판단하면 된다. 2. 떠있는 미네랄들에 대해서 아랫부분이 어딘가에 닿을 때까지 떨어뜨린다. 1에서 검증한 떠있는 미네랄들에 대해서 각각 아랫부분이 어딘가에 닿으려면 몇 칸이나 떨어져야 하는지 구한다. 떠있는 클러스터는 그중 가장 작은 값만큼 떨어지게 될 것이다. #include #include using namespace std; const int LEFT = 0, RIG.. 2022. 7. 8. 백준 10974번 모든 순열 - C++ 풀이 1. DFS를 사용하여 모든 순열을 구한다. 2. DFS 과정에서 각 숫자의 사용 여부는 비트 마스크로 나타낼 수 있다. 1. DFS를 사용하여 모든 순열을 구한다. DFS를 돌면서, 매 depth마다 선택한 적 없는 숫자 중 하나의 숫자를 선택하면 모든 순열을 구할 수 있다. 2. DFS 과정에서 각 숫자의 사용 여부는 비트 마스크로 나타낼 수 있다. 이때 각 숫자를 이전 depth에서 선택했었는지 여부를 비트 마스크로 나타내어 준다. #include #include using namespace std; int N; vector permu; void DFS(int depth, int mask) { if (depth == N) { for (auto x : permu) cout 2022. 6. 23. 백준 2251번 물통 - C++ 풀이 1. 모든 상황의 경우의 수는 200*200*200가지이다. 2. 각 상황에서 x물통에서 y물통으로 물을 붓는 모든 경우를 시도하면서 가능한 상황을 모두 구해준다. 1. 모든 상황의 경우의 수는 200*200*200가지이다. 각 물통의 최대 용량은 200이므로 세 물통에 물이 담기는 경우의 수는 N^3가지이다. 2. 각 상황에서 x물통에서 y물통으로 물을 붓는 모든 경우를 시도하면서 가능한 상황을 모두 구해준다. DFS를 이용하여 계속해서 물을 붓는 시뮬레이션을 해준다. DFS(a, b, c) = 현재 세 물통에 a, b, c리터의 물이 담겨있는 상황이라고 하자. 현재 상황에서 물을 붓는 경우는 a -> b, a -> c, b -> a, b -> c, c -> a, c -> b로 총 6가지 이다. 각 경.. 2022. 6. 11. 백준 13023번 ABCDE - C++ 풀이 1. 주어진 조건의 ABCDE가 존재하려면 주어진 그래프에 depth가 4 이상인 구간이 있어야 한다. 2. 모든 가능한 DFS를 시도하면서 depth가 4 이상이 되는 경우가 있는지 확인한다. 1. 주어진 조건의 ABCDE가 존재하려면 주어진 그래프에 depth가 4 이상인 구간이 있어야 한다. 주어진 ABCDE의 관계를 나타내면 A -> B -> C -> D -> E이다. 이렇게 5개의 정점이 쭉 연결된 구간이 있다는 것은 그래프의 높이가 4 이상이라는 의미이다. 2. 모든 가능한 DFS를 시도하면서 depth가 4이상이 되는 경우가 있는지 확인한다. 인접한 정점이 여러개일 때 방문 순서에 따라 depth가 달라지기 때문에 모든 경우를 다 시도해보아야 한다. 시작 정점에 따라서도 depth가 달라지기.. 2022. 6. 8. 백준 13459번 구슬 탈출 - C++ 풀이 1. 시뮬레이션으로 10번 이내로 움직이는 모든 경우를 다 시도해본다. 1. 시뮬레이션으로 10번 이내로 움직이는 모든 경우를 다 시도해본다. 시뮬레이션 문제였다. 보드 기울여 구슬 움직이는 것을 잘 구현해준 뒤, DFS를 이용해서 10번 이내로 움직이는 모든 경우를 다 시도해준다. 각 depth에서 상하좌우로 움직이는 경우 전부를 시도해주어야 한다. #include #include using namespace std; const int MAX = 10; const int U = 0, D = 1, L = 2, R = 3; const int RED = 100, BLUE = 200; struct Marble { int r, c; char color; }; int N, M; Marble H; char boar.. 2022. 6. 3. 이전 1 2 3 4 5 6 다음 반응형
