목록백트래킹 (50)

1일1알

백준 15683번 감시 C++

은근히 고려해야 할게 많은 쉽지는 않은 구현 문제이다. 각각의 cctv마다 감시할 수 있는 경우의 수가 다르다. 예를 들면, 1번 cctv는 상, 하, 좌, 우 4가지 경우를 감시할 수 있고, 2번 cctv는 상하, 좌우 2가지 경우를 감시할 수 있다. 이 경우들을 비트로 만들어서 저장하였다. 위, 오른쪽, 아래, 왼쪽 순서로 저장했고 감시할 수 있으면 1, 못하면 0으로 저장했다. 2번 cctv의 경우는 상하, 좌우 2가지 경우가 있기 때문에 1010, 0101 두 개를 저장했다. 다음은 백트래킹을 이용하여 모든 경우를 탐색했는데, 중간에 마스크를 이용해서 감시할 수 있는 지역을 알아냈다. 마스크는 1000부터 시작하여 오른쪽으로 한 칸씩 옮겨가는데, 각 경우마다 cctv와 &연산을 해서 0이 아니라면..
알고리즘 2022. 1. 7. 12:55
백준 15686번 치킨 배달 C++

백트래킹을 이용하여 치킨집이 m개일 모든 경우를 구하고, 각 경우마다 각 집에서 가장 가까운 치킨집의 거리의 합 중 최솟값을 구하는 방식으로 문제를 해결하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int n, m; vector houses; vector wholeChickens; vector myChickens; int ans = 987654321; int GetDist() { int sum = 0; for (auto house : houses) { int ..
알고리즘 2021. 12. 31. 13:56
백준 14502번 연구소 C++

백트래킹을 이용하여 벽을 3개를 세운 모든 경우를 구하고 각 경우마다 bfs를 통해 바이러스가 퍼지는 것을 시뮬레이션 한 뒤, 그 중 안전지대가 가장 많이 나온 경우를 출력하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int n, m; vector v(8, vector(8, 0)); vector visited(8, vector(8, false)); int ans = -1; int wall = 3; int posR[4] = { -1,0,1,0 }; int pos..
알고리즘 2021. 12. 28. 12:33
백준 16987번 계란으로 계란치기 C++

백트래킹을 이용하여 가능한 모든 경우를 구하고 그 경우들 중에서 계란이 가장 많이 깨진 개수를 구하면 된다. 처음에 문제를 풀때 현재 잡은 계란의 오른쪽 계란만 깰 수 있다고 생각하고 풀어서 답이 안나왔다. 그래서 문제를 다시 읽어보니 그런 조건이 없어서 모든 경우를 탐색하도록 바꿨더니 문제가 풀렸다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int n; vector v(8); int ans = 0; void BT(int index) { if (index >= n..
알고리즘 2021. 12. 23. 12:13
백준 1342번 행운의 문자열 C++

백트래킹을 이용하여 위치를 재배치한 모든 문자열을 구할 수 있다. 첫 번째 예제는 abababa 라는 문자열 하나만 행운의 문자열이지만, 답을 구해보면 144가 나오는데, 그 이유는 abababa 라는 문자가 144번 중복되어서 나오기 때문이다. 이를 해결하기 위해 a의 개수 4, b의 개수 3을 팩토리얼 연산을 하고 곱해준 뒤 답에서 나눠주어야 한다. 4! = 24, 3! = 6이고 24*6 = 144이다. 처음에 구한 답이 144이고 이것을 144로 나누면 1이 나온다. 알파벳의 각각의 개수의 정보를 저장하는 데 unordered_map 자료구조를 사용하였다. #include #include #include #include #include #include #include #include #includ..
알고리즘 2021. 12. 3. 13:01
백준 18428번 감시 피하기 C++

백트래킹을 이용하여 빈 칸에 3개의 장애물을 놓는 모든 경우를 만들고 각각의 경우마다 배열을 검사하면서 하나의 경우라도 선생님의 감시를 피할 수 있다면 YES, 하나도 피할 수 없다면 NO를 출력하도록 구현하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int n; char arr[6][6]; bool isPossible = false; int posR[4] = { -1,0,1,0 }; int posC[4] = { 0,1,0,-1 }; bool IsMeet() ..
알고리즘 2021. 11. 27. 14:08
이전 Prev 1 ··· 5 6 7 8 9 Next 다음