본문 바로가기
반응형

dfs26

백준 2210번 숫자판 점프 - C++ 풀이 1. DFS를 사용하여 인접한 칸으로 5번 이동하는 모든 경우를 구한다. 1. DFS를 사용하여 인접한 칸으로 5번 이동하는 모든 경우를 구한다. 5번 이동하므로 총 탐색해야 하는 상태 수는 25 * (4^5)로 매우 적기 때문에 브루트 포스로 해결할 수 있다. DFS를 통해 모든 경우를 구해서, 만들 수 있는 모든 수를 구해준다. #include #include using namespace std; int board[5][5]; unordered_set st; int dr[] = {-1, 1, 0, 0}; int dc[] = {0, 0, -1, 1}; void DFS(int n, int r, int c, int curr) { if (n == 6) { st.insert(curr); return; } fo.. 2022. 9. 6.
백준 17142번 연구소 3 - C++ 풀이 1. M개의 자리를 활성시키는 모든 경우를 시뮬레이션하여 최소 시간을 구한다. 2. 각 경우는 BFS를 이용해서 시뮬레이션한다. 1. M개의 자리를 활성시키는 모든 경우를 시뮬레이션하여 최소 시간을 구한다. 바이러스를 놓을 수 있는 위치가 최대 10군데이고, M이 최대 10이므로 최악의 경우에도 10C5가지 경우 밖에 발생하지 않는다. 또한 각 경우를 시뮬레이션하는 데는 O(N^2)의 시간 복잡도가 들기 때문에 브루트 포스를 사용해도 충분하다. 2. 각 경우는 BFS를 이용해서 시뮬레이션한다. 바이러스가 퍼지는 시뮬레이션은 BFS를 사용하면 쉽게 구현할 수 있다. #include #include #include using namespace std; typedef pair pii; const int EMP.. 2022. 8. 19.
백준 2234번 성곽 - C++ 풀이 1. DFS/BFS를 사용해서 방의 개수를 센다. 2. DFS/BFS를 사용해서 각 방의 넓이를 구한다. 3. 2에서 구한 값을 사용하여 모든 벽에 대해 해당 벽을 제거했을 때 얻을 수 있는 방의 크기를 구한다. 1. DFS/BFS를 사용해서 방의 개수를 센다. 방의 개수는 연결 요소의 개수와 같다. DFS나 BFS를 사용하여 연결 요소의 개수를 세준다. 2. DFS/BFS를 사용해서 각 방의 넓이를 구한다. 각 방의 넓이는 각 연결 요소의 크기와 같다. 똑같이 DFS나 BFS를 사용해서 구할 수 있다. 3. 2에서 구한 값을 사용하여 모든 벽에 대해 해당 벽을 제거했을 때 얻을 수 있는 방의 크기를 구한다. 하나의 벽을 제거하면 두 칸이 이어지므로 최대 두 개의 방이 하나로 합쳐질 수 있다. 따라서 벽.. 2022. 8. 2.
백준 1113번 수영장 만들기 - C++ 풀이 1. 하늘에서 비를 내린다고 생각하고, 낮은 칸부터 물을 채운다. 2. 바깥에서 시작하는 DFS/BFS로 물이 담기지 않고 밖으로 흐르는 칸을 체크한다. 1. 하늘에서 비를 내린다고 생각하고, 낮은 칸부터 물을 채운다. 하늘에서 비를 내린다고 생각하자. 낮은 칸부터 점차 물이 차오를 것이다. 이것을 시뮬레이션해준다. 2. 바깥에서 시작하는 DFS/BFS로 물이 담기지 않고 밖으로 흐르는 칸을 체크한다. 비가 내려도 담기지 않고 밖으로 흐르는 칸이 있을 수도 있다. 바깥 칸에서 시작해서 현재 높이 이하인 칸만 방문하는 DFS/BFS를 수행했을 때, 방문되는 칸이라면 밖으로 흐르는 칸이다. #include #include using namespace std; int N, M; int board[52][52].. 2022. 7. 20.
백준 2610번 회의준비 - C++ 풀이 1. 각 사람이 리더일 때 의사전달시간의 최댓값은 플로이드 와샬 알고리즘을 사용하여 구할 수 있다. 2. 위원회는 그래프의 연결 요소와 같다. 3. DFS/BFS를 사용하여 각 위원회의 리더를 정한다. 1. 각 사람이 리더일 때 의사전달시간의 최대값은 플로이드 와샬 알고리즘을 사용하여 구할 수 있다. A가 리더일 때 B의 의사전달시간은 A와 B의 사이의 거리와 같다. 따라서 A가 리더일 때 의사전달시간의 최댓값은 나머지 모든 사람들과의 거리를 알면 구할 수 있다. 플로이드 와샬 알고리즘을 사용하여 모든 사람들에 대해 각 사람이 리더일 때의 의사전달시간의 최댓값을 구할 수 있다. 2. 위원회는 그래프의 연결 요소와 같다. 위원회의 정의는 그래프의 연결요소와 같다. 따라서 K는 연결요소의 수와 같다. 3. .. 2022. 7. 15.
반응형

티스토리툴바